Wyszukiwanie binarne dla bystrzaków

Na wtorkowym (31 marca 2020) pojawiła się prośba aby zaprezentować problem binarnego wyszukiwania. Powstał gotowy program korzystający z polecenia goto (który powinien być najpierw przerobiony tak aby wykorzystywał jakieś polecenie pętlowe, a później został zaprogramowany jako funkcja).

Problem postawiony jest tak:

  1. Mamy tablicę (dowolnego typu) zawierającą dowolne wartości wpisane w kolejności rosnącej (albo malejącej).
  2. Mamy też wartość x i mamy sprawdzić czy wartość ta znajduje się w tablicy1 czy nie (a w wersji zaawansowanej) gdzie powinna być wstawiona.

Omówię powstały program:

Początek jest dosyć standardowy:

 

Żeby ułatwić sobie modyfikację danych, tablicę zadeklarowałem tak:

 

Nie podałem jej długości, zamiast tego wpisałem kolejne wartości co ułatwi wprowadzanie zmian polegających na przykład na „skróceniu ” tablicy, które można zrealizować za pomocą wstawienia znaku komentarza: 1, 10, // 123, 200, 1000, 2000 (wszystkie liczby po znakach // „znikają”).

Pozostaje natomiast problem znajomości rozmiaru tablicy. Wykorzystałem tu polecenie języka C sizeof(). Podaje one liczbę bajtów, którą zajmuje w pamięci obiekt będący argumentem polecenia. Zatem sizeof(D) poda długość (w bajtach) tablicy D, a sizeof(int) poda długość w bajtach każdego elementu (zmienna, stała) typu int. Podzielenie tych wartości powinno dać liczbę elementów tablicy.

Teraz deklaracja pozostałych zmiennych:

 

x to szukana wartość, ab to początek i koniec zakresu poszukiwań (zaczynamy od całej tablicy), c to srodek przedziału , który będzie wyliczany po każdej zmianie zakresu.

 

Ponieważ będę korzystał z polecenia goto musiałem wprowadzić etykietę (poczatek:) tam gdzie cykl się rozpoczyna.

Sprawdzam najpierw czy (przypadkiem) nie odnalazłem już szukanej wartości. Jeżeli tak można skończyć obliczenia (goto koniec;).

W przeciwnym razie, trzeba zdecydować, którą połówkę tablicy trzeba odrzucić:

 

Jeżeli środkowa wartość tablicy jest większa niż wartość szukana to odrzucamy prawą część tablicy (wraz ze środkiem, bo już wcześniej upewniliśmy się, że nie ma tam wartości szukanej…); w przeciwnym razem odrzucamy „lewą” część tablicy wraz ze środkiem.

W tym miejscu moglibyśmy już przejść na początek, żeby kontynuować obliczenia. Ale obliczenia nie mogą trwać w nieskończoność (jak było to w przypadku szukania miejsca zerowego metodą połowienia, tam przedział mógł się skracać i skracać). Teraz operujemy na liczbach całkowitych.

W przypadku gdy nie możemy w tablicy znaleźć szukanej wartości obliczenia należy kontynuować tylko jeżeli a <= b; zatem

 

Jeżeli znaleźliśmy się w tym miejscu możemy napisać, że liczby nie znaleziono i skończyć program

 

Gdy liczbę znaleziono, kończyliśmy pętle „wyskakując” z niej do etykiety koniec:

 

co kończy program.


  1. I na którym miejscu.