Wyszukiwanie binarne

Wyszukiwanie binarne jest algorytmem opierającym się na metodzie dziel i zwyciężaj, który w czasie logarytmicznym stwierdza, czy szukany element znajduje się w uporządkowanej tablicy i jeśli się znajduje, podaje jego indeks.

Czas pracy
Na przykład w zbiorze zawierającym 1.000.000.000 elementów algorytm wyszukiwania binarnego wykona maksymalnie 30 porównań , podczas gdy algorytm wyszukiwania liniowego (metoda ,,naiwna") będzie maksymalnie musiał wykonać 1.000.000.000 porównań.

Metoda
Uporządkowaną tablicę dzielimy na coraz mniejsze kawałki (przedziały) do momentu, gdy znajdziemy szukany element bądź przedział będzie zerowej długości (brak elementu). Rozpoczynamy od pełnej tablicy, czyli lewy koniec przedziału ustawiamy na początek tablicy a prawy na koniec. Następnie "celujemy" w środek przedziału i odczytujemy wartość. Jeśli jest równa szukanemu elementowi to koniec, znaleźliśmy element, oprócz tego są możliwe dwa przypadki. Jeśli odczytana wartość jest większa od szukanej oraz tablica jest uporządkowana niemalejąco (odpowiednio malejąco), prawy (lewy) koniec przedziału ustawiamy na odczytaną wartość. W drugim przypadku - odczytana wartość mniejsza - postępujemy analogicznie, czyli: lewym (prawym) końcem przedziału staje się "środkowy" element. Algorytm wykonujemy tak długo, aż znajdziemy szukany element bądź lewy koniec "znajdzie się" za prawym końcem.

Przytoczona wcześniej metoda tłumaczy wyszukiwanie binarne w dość ogólny sposób. Niestety (albo i stety) algorytm ten ma wiele różnych wersji, więc chociażby pojęcie "środkowy" staje się wysoce względne.

[def. by slic3]

Przykładowa funkcja w C++ (thx to Maciek 'Crezax' Piekarz)

    p=0;        // Szukamy liczby w przedziale [p,q]. Na początku jest to [0,n-1], ale to się będzie zmieniać.
    q=n-1;   
    while (p<q)    // Dopóki lewy i prawy koniec przedziału się nie zejdą, czyli dopóki mamy jeszcze gdzie szukać...
    {
        int s=(p+q)/2;     // Liczba s to środek przedziału, popatrzmy, co tam jest.
        if (tab[s]>=x)    // Jeśli w środku jest element większy lub równy x...
            q=s;        // ...to cała druga połowa, od s do q jest niepotrzebna, przesuwamy prawy kraniec do s.
        else            // W przeciwnym wypadku...
            p=s+1;        //  ...niepotrzebna jest pierwsza połowa, w przedziale [p,s] na pewno nie ma x.
    }

Zauważmy, że jeśli w tablicy są jakieś liczby x, to pierwsza z nich będzie zawsze pozostawać między p a q. A zatem na końcu algorytmu w tablicy pod indeksem p będzie pierwsze wystąpienie elementu x. Jeśli x nie było w tablicy, to pod indeksem p będzie pierwsza liczba większa od x.

Może się niekiedy przydać wersja algorytmu, która znajduje ostatnie wystąpienie x w tablicy. W tym celu trzeba kod zmienić następująco:
Jeśli pod tab[s] znajduje się coś mniejszego lub równego x, to ostatnie wystąpienie x na pewno jest na prawo od s i możemy przesunąć lewy kraniec do s. W przeciwnym wypadku przesuwamy prawy kraniec do s-1. Aby to nie wieszało się na danych wielkości 2, konieczne jest zaokrąglanie w górę (s = (p+q+1)/2), nie w dół.


Luki92

Proponuję jeszcze rozwiązanie rekurencyjne:

int binarne(int x,int y,int z)
{
   if(x==y)if(tab[x]==z)return x;else return 0;
   if(tab[(x+y)>>1]>=z)return binarne(x,(x+y)>>1,z);
                  else return binarne(1+(x+y)>>1,y,z);
}

Rozwiązanie wywołuje samo siebie, dla mniejszych kawałków. Jeśli rozmiar kawałka jest 1, dopiero wtedy sprawdza czy dany element
występuje. tab[(x+y)»1] to jest środkowy element danego kawałka. z to jest szukana liczba. x oraz y: indeksy tablicy "od" i "do".
Funkcja zwróci indeks tablicy, gdzie wystąpił dany element, albo 0, jeśli takiego nie ma.

Wywołanie:

wynik=binarne(1,n,szukana);

Różnicą w stosunku do poprzedniego rozwiązania jest numeracja w tablicy. Tutaj jest od 1..n, wcześniej było 0..n-1.

Proszę o info. w przypadku błędów w kodzie(ew. innych).

//Jeśli chcesz, to stosuj na siłę rekurencję, jednak ja, jeśli miałbym wybrać między czytelnością,
a niepotrzebną złożonością, wybrałbym to pierwsze, po za tym, co zyskamy stosując tu
rekurencję?? Raczej nic, ani nie poprawimy wydajności, a kod niby krótszy, ale mniej czytelny :(
Maciek "Crezax"

To zależy jak kto lubi:)
Łukasz M.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License