ALG8

48 Rozdział 2. Rekurencja

W celu dokładniejszego przeanalizowania algorytmu posłużymy się kilkoma zmiennymi pomocniczymi:

•    left indeks tablicy ograniczający obserwowany obszar tablicy od lewej strony;

•    riglit indeks tablicy ograniczający obserwowany obszar tablicy od prawej strony;

0	1	2	3	4	5	6	7	B	9	10	11
I	2	6	IX	20	23	29	32	34	39	40	41

Ietl=0,    f, md=(!e/i+riQh!)/2= 5. tabfmidt=23

Rys. 2 - 9.

Przeszukiwanie binarne nu przykładzie.

I8<23    18-23    I8>23

I

2

6

I8

20

23

29

32

34

39

40

41

teft=0, ńght=mid=4, micf=(łeft^ńght)/2=2. tablmidpS

I

2

6

18

20

23

29

32

34

39

40

41

iett=mid=2, righF4. rmd=(left+right)/2=3. tab(midl=18

I8<!8 ,    18-18    I8>I8

• niid indeks elementu środkowego obserwowanego aktualnie obszaru tablicy.

Na rysunku 2-9 przedstawione jest działanie algorytmu oraz wartości zmiennych left, right i miel podczas każdego ważniejszego etapu. Poszukiwanie zakończyło się pomyślnie już po trzech etapach". Warto zauważyć, że to samo zadanie, rozwiązywane za pomocą przeglądania od lewej do prawej elementów tablicy, zostałoby ukończone dopiero po 4 etapach. Być może otrzymany zysk nie oszałamia, proszę sobie jednak wyobrazić, co by było, gdyby tablica miała rozmiar kilkanaście razy większy niż len użyty w przykładzie?! Proszę napisać funkcję, która realizuje poszukiwanie binarne w sposób rckurencyjny.

² Za „etap” będziemy tu uważali moment testowania, czy dana liczba jest tą, której poszukujemy.