ALG0

190 Rozdział 7. Algorytmy przeszukiwania

Odnalezienie liczby .1 w tablicy tub jest sygnalizowane poprzez wartość funkcji; jeśli jest to liczba z przedziału 0... n-1, wówczas jest po prostu indeksem komórki, w której znajduje się x. W przypadku zwrotu liczby w jesteśmy informowani, iż element x nie został znaleziony. Zasada obliczania wyrażeń logicznych w C++ gwarantuje nam, że podczas analizy wyrażenia (i<n) && (Kih[i]!=.\) w momencie stwierdzenia fałszu pierwszego czynnika iloczynu logicznego reszta wyrażenia - jako nie mająca znaczenia nie będzie już sprawdzana. W konsekwencji nie będzie badana wartość spoza zakresu dozwolonych indeksów tablicy, co jest tym cenniejsze, iz. kompilator C++ w żaden sposób o tego typu przeoczeniu by nas nie poinformował.

W tym miejscu wypada jeszcze uściślić, że ten typ przeszukiwania, polegający na zwykłym sprawdzaniu elementu po elemencie, jest metodą bardzo wolno działającą. Winna być ona stosowana jedynie wówczas, gdy nie posiadamy żadnej informacji na temat struktury przeszukiwanych danych, ewentualnie sposobu ich składowania w pamięci. Jest oczywiste, iż dowolny algorytm przeszukiwania liniowego jest klasy C)(n)\

7.2. Przeszukiwanie binarne

Jak już zostało zauważone w paragrafie poprzednim, ewentualna informacja na temat sposobu składowania danych może być niesłychanie użyteczna podczas przeszukiwania. W istocie często mamy do czynienia z uporządkowanymi już w pamięci komputera zbiorami danych: np. rekordami posortowanymi alfabetycznie, według niemalejących wartości pewnego pola rekordu etc. Zakładamy zatem, że tablica jest posortowana, ale jest to dość częsty przypadek w praktyce, bowiem człowiek lubi mieć do czynienia z informacją uporządkowaną. W takim przypadku można skorzystać z naszej „meta-wiedzy" w celu usprawnienia przeszukiwania danych. Łatwo możemy bowiem wyeliminować z poszukiwań te obszary tablicy, w których element x na pewno nie może się znaleźć. Dokładnie omówiony przykład poszukiwania binarnego znalazł się już w rozdziale 2 - patrz zad. 2-2 i jego rozwiązanie. W tym miejscu możemy dla odmiany podać iteracyjną wersję algorytmu:

bimiry-i.cpp

int szukaj(int tab[],int x)

I

enum [TAK,NIE| Znalazlem=NIS;

int left=0, rriqht=n-l,mid;

whilo (lcft<-rig'nt ££ Znalazłem!-TAK)

I

mid=(left+cight)/2; if(tab|nid)==x)