Wyszukiwanie binarne – Algorytm typu „dziel i zwyciężaj”

Wyszukiwanie binarne to jeden z najpopularniejszych algorytmów do wyszukiwania danych w tablicy posortowanych liczb. Algorytm ten został oparty o metodę „dziel i zwyciężaj” dzięki czemu potrafi w czasie logarytmicznym znaleźć szukaną liczbę oraz zwrócić jej indeks jeśli oczywiście została odnaleziona. Dla przykładu przy tablicy liczb która zawiera milion elementów wyszukiwanie binarne do odnalezienia żądanej liczby potrzebuje wykonać zaledwie 20 porównań. Oczywiście aby to wszystko zadziałało przeszukiwana tablica musi zostać wcześniej posortowana.

Ogólna zasada działania algorytmu wyszukiwania binarnego polega na „dzieleniu” tablicy liczb na połowę i sprawdzaniu czy element znajdujący się dokładnie po środku jest elementem szukanym, jeśli nie to czy jest większy lub mniejszy. W ten sposób bardzo szybko zawężamy zakres poszukiwań, aż w końcu natrafimy na element który poszukujemy lub po prostu go nie znajdziemy. W pesymistycznym przypadku nasz program będzie miał złożoność czasową logn gdzie n to długość przeszukiwanej tablicy.

Przykładowa funkcja wyszukiwania binarnego napisana w języku Java operująca na tablicy o nazwie: tablicaLiczb:

A co jeśli liczby w tablicy się powtarzają?

Ta podstawowa wersja algorytmu wyszukiwania binarnego sprawdza się wtedy kiedy na przykład dane występujące w tablicy nie powtarzają się lub nie interesuje nas ilość wystąpień szukanej liczby oraz indeks np. pierwszego lub ostatniego wystąpienia. Prosta modyfikacja algorytmu wyszukiwania binarnego pozwoli nam ominąć ten problem. Zamiast odnajdywania jakiegokolwiek elementu będziemy szukać jego pierwszego lub ostatniego wystąpienia.

Aby odnaleźć pierwsze wystąpienie danej liczby w tablicy będziemy wykorzystywać podstawową wersję algorytmu wyszukiwania binarnego ale kiedy już trafimy na szukany element to będziemy sprawdzać czy ten wcześniejszy o indeksie mniejszym o 1 też jest szukaną cyfrą. Jeżeli tak to musimy „przenieść się” do podzbioru na lewo wyznaczyć nowy środek i tak w kółko dopóki nie znajdziemy szukanego elementu przed którym nie będzie liczby którą szukamy. Oczywiście natrafienie na element o indeksie 0 kończy całą procedurę bowiem wiadomo iż wcześniej nie ma żadnych liczb.

Przykładowa implementacja przerobionej wersji algorytmu wyszukiwania binarnego służąca do znalezienia pierwszego wystąpienia szukanej liczby. Fragment programu (w całości dostępny jest na końcu tego artykułu) napisany w języku Java:

Analogiczną procedurę zastosujemy do znalezienia ostatniego wystąpienia szukanej liczby tyle, że teraz zamiast przesuwać się na lewo będziemy przesuwali się w prawo, aż do momentu kiedy taki warunek: tablicaLiczb[i + 1] != szukanaLiczba, zostanie spełniony.

Przykładowy implementacja przerobionej wersji algorytmu wyszukiwania binarnego służąca do znalezienia ostatniego wystąpienia szukanej liczby. Fragment programu (w całości dostępny jest na końcu tego artykułu) napisany w języku Java:

Teraz mając indeks pierwszego oraz ostatniego wystąpienia szukanej liczby można na przykład określić ilość jej powtórzeń.

Przykładowy program oparty o wyszukiwanie binarne zliczający ilość wystąpień danej liczby w posortowanej rosnąco tablicy (jeżeli szukana liczba nie występuje wypisywany jest komunikat: „Szukana liczba nie została odnaleziona.”):

Fot. (ilustracja wpisu): ideonexus.com, Flickr | CC.

, , , , , ,

  • ms

    W pierwszym przykładzie użycie czyZnalezione tylko go komplikuje.
    Wystarczyło napisać if(tablicaLiczb[srodek] == szukanaLiczba) return srodek;

    • Faktycznie można tam po prostu zwrócić srodek i zakończyć działanie, ale ja bym tego nie nazwał dodatkową komplikacją kodu ;-) Ale jeżeli utrudnia to komuś zrozumienie tego algorytmu to poprawię na taką wersję.