Wyszukiwanie binarne dla bystrzaków

(Kiedyś tam) 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 tablicy¹ czy nie (a w wersji zaawansowanej) gdzie powinna być wstawiona.

Omówię powstały program:

Początek jest dosyć standardowy:

#include <stdio.h>
int main(int argc, char **argv)
{

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

    int t[] = {
        1, 10, 123, 200, 1000, 2000
    };
    int n = sizeof( t ) / sizeof( int );

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:

    int x = -1;
    int a, b, c;
    a = 0;
    b = n - 1;

x to szukana wartość, a i b 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.

poczatek:
    c = ( a + b ) / 2;
    if ( t[c] == x )
        goto koniec;

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ć:

    else if ( t[c] > x )
        b = c - 1;
    else
        a = c + 1;

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

    if ( a <= b )
        goto poczatek;

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

    printf("nie ma\n");
    return 1;

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

koniec:
    printf("wartosc jest w tablicy na miejscu %d\n", c);
    return 0;
}

co kończy program.