wyszukiwanie
Trochę ciekawostek – na weekend (czego to ludzie nie wymyślą ...
Wyszukiwanie sekwencyjne i binarne
Zwykle gdy chcesz odnale¼æ w tablicy liczb jaki¶ element sprawdzasz po kolei wszystkie pola.
Je¶li liczby w tablicy nie s± w ¿aden sposób posortowane, nie ma lepszego sposobu. Jest to wyszukiwanie sekwencyjne.
Gdy natomiast mamy do czynienia z tablic± posortowan±, du¿o lepiej jest u¿yæ algorytmu wyszukiwania binarnego. Przypomina on zabawê w zgadywanie liczb... Ale chyba lepiej pokazaæ to na prostym przyk³adzie.
Mamy tablicê 5 liczb: 1, 4, 89, 100, 250. Za³ó¿my, ¿e szukam liczby 89. Bierzemy najmniejsz± potêgê dwójki wiêksz± od piêciu (liczby elementów tablicy). Jest to 8. DELTA := 8.
Indeks - numer komórki tablicy, któr± odczytujemy - bêdê trzyma³ w zmiennej I.
Na pocz±tku I := 1. Tablica[1] < 89, dlatego dzielê deltê na 2 i powiêkszam o ni± I. Wiêc:
I := 1 + 4 = 5
Pi±ty element tablicy jest z kolei za du¿y, dlatego po podziale delty na 2, I zostaje o ni± pomniejszone:
I := 5 - 2 = 3
Trzecim elementem jest rzeczywi¶cie 89. Sukces.
Powy¿szy przyk³ad to wersja iteracyjna. Du¿o ³atwiejsza do zapisania - bez pomy³ki - jest jednak wersja rekurencyjna. Najpierw sprawdzany jest ¶rodkowy element ci±gu. Je¶li szukany element jest od niego mniejszy, nastêpuje rekurencyjne wywo³anie dla lewej czê¶ci ci±gu. Je¶li jest wiêkszy, dla prawej czê¶ci. Je¶li jest równy, to znaczy, ¿e odnaleziono poszukiwan± liczbê. Gdy w ci±gu nie wystêpuje szukana liczba, nast±pi b³êdne wywo³anie procedury (z "zamienionymi" ogranicznikami). Wersja s³owna jest dosyæ nieprzystêpna, ale kod ¼ród³owy (mam nadziejê) nie pozostawia ¿adnych w±tpliwo¶ci.
// djgpp
// Ostrzegam, ¿e dopiero zaczynam naukê c++. :))
// Poni¿szy program porównuje wyniki wyszukiwania tych 2 procedur
// i algorytmu naiwnego w wielu przypadkowych konfiguracjach.
// Mo¿esz traktowaæ to jako dowód niezawodno¶ci.
#include <conio.h>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
const long int max_size = 1000;
int tab[max_size];
long int w_bin_iterac(int tab[], long int a, long int b, int s);
long int w_bin_rekur (int tab[], long int a, long int b, int s);
long int w_naiw(int tab[], long int a, long int b, int s);
// a,b - pocz±tek i koniec przedzia³u
int main()
{
long int j,k,l,tmp=rawclock(),m,p,q,s,n;
clrscr();
srandom(tmp);
for (n=1; n=1;}
if (delta==0 && (((i>b || i<a)) || tab[i]!=s)) return -1;
if (s < tab[i]) {i-=delta; delta>>=1;}
else
{if (s > tab[i]) {i+=delta; delta>>=1;}
else return i;}
}
}
long int w_bin_rekur(int tab[], long int a, long int b, int s)
{
long int sred;
if (a>b) return -1;
sred=(a+b) >> 1;
if (s==tab[sred]) return sred;
if (s< tab[sred]) return w_bin_rekur(tab, a, sred-1, s);
else return w_bin_rekur(tab, sred+1, b, s);
}
long int w_naiw(int tab[], long int a, long int b, int s)
{
for (long int i=a; i