Algorytm wyszukiwania binarnego

Z racji, że obecnie na studiach mam przedmiot nazywający się Algorytmy i Struktury Danych, postanowiłem opisywać te pierwsze tutaj na blogu. Po pierwsze w celu własnego utrwalenia wiedzy, gdyż jedną z najlepszych metod nauki jest ta opisana przeze mnie na blogu. A poza tym, może mój sposób opisu przypadnie właśnie Tobie do gustu? Zatem jedziemy!

Algorytm wyszukiwania binarnego jak sama nazwa wskazuje służy do wyszukiwania. Za jego pomocą możemy wyszukiwać np. liczby w tablicy. Jest to bardzo prosty algorytm. Polega on na dzieleniu przeszukiwanej tablicy na pół i porównywaniu elementu środkowego z szukaną wartością. Ale po kolei.

Załóżmy że do przeszukania mamy następującą tablicę:

Jak widać warunki wejściowe algorytmu są następujące:

• Tablica wejściowa musi mieć >= 0 elementów
• Tablica wejściowa musi być posortowana niemalejąco

Na wyjściu natomiast otrzymujemy: indeks szukanego elementu, jeśli taki istnieje w zadanej tablicy. Jeśli nie, otrzymujemy stosowną wartość to oznaczającą. Najczęściej będzie to liczba -1.

Przejdźmy więc do kroków jakie należy wykonać, aby stwierdzić na której pozycji znajduje się szukana przez nas liczba:

1. Wybieramy  środkowy element tablicy.  W praktyce oznacza to podzielenie ilości elementów tablicy na dwa. I wzięcie elementu z tym indexem.
2. Sprawdzamy, czy wybrany element jest równy szukanemu elementowi. Jeśli tak, zwracamy jego pozycje i kończymy szukanie. Jeśli nie to z naszej tablicy tworzymy podtablicę na takiej zasadzie:
   • Jeśli natomiast element środkowy jest większy niż szukany przez nas, to zawężamy tablicę do jej lewej strony. Czyli bierzemy elementy od lewego krańca do obecnie środkowego elementu.
   • Jeśli element środkowy jest mniejszy niż ten szukany przez nas, to zawężamy tablicę do jej prawej strony. Czyli bierzemy elementy od obecnie środkowego elementu do prawego końca tablicy.
3. Punkty 1. i 2. powtarzamy do momentu znalezienia szukanego elementu. Jeśli to nie nastąpi zwracamy -1 lub inną wartość oznaczającą brak szukanego elementu.

Prześledźmy więc cały proces na przykładzie powyższej tablicy. Załóżmy, że szukaną liczbą jest 3096.

Ilość elementów tablicy to 10. Środkowy element ma zatem indeks 5. Zatem środkowy element ma wartość 107. Widać, że 107 < 3096. Musimy wziąć zatem prawą stronę tablicy. Wygląda ona tak:

Środkowym elementem teraz jest element o wartości 900. Jest ona znów mniejsza niż 3096. Zatem znów zawężamy tablicę do jej lewej strony:

Elementem „środkowym” jest teraz element o wartości 1024. Gdyż: długość tablicy to 2. 2/2 = 1. Jak widać jest ona znowu mniejsza od szukanej przez nas wartości 3096. Po raz kolejny zawężamy tablicę do jej lewej strony:

3096

W tym przypadku mamy tylko jeden element, więc jest on automatycznie środkowym. Porównujemy go z szukaną wartością. Tak mamy to! Możemy więc zwrócić 10 jako pozycja szukanego przez nas elementu.

Jeżeli natomiast w ostatnim kroku okazałoby się, że ten jeden pozostały element nie jest szukanym przez nas, to należałoby uznać, że w zadanej tablicy nie ma szukanej przez nas liczby.

Teraz implementacja w dwóch językach programowania:

• Java

public static int search(int[] array, int searchNumber)
    {
        int right = 0;
        int left = array.length - 1;

        while(left <= right)
        {
            int currentPosition = left + (right-left)/2;

            if(array[currentPosition] == searchNumber)
            {
                return currentPosition;
            }

            if(array[currentPosition] > searchNumber)
            {
                right = currentPosition - 1;
            }
            else if(array[currentPosition] < searchNumber)
            {
                left = currentPosition + 1;
            }
        }

        return -1;
    }

• C#

public int Sort(int[] vector, int search)
        {
            int left = 0;
            int right = vector.Length - 1;

            while (left <= right)
            {
                int currentPosition = left + ( right - left )/2;

                if (vector[currentPosition] == search)
                {
                    return currentPosition;
                }

                if (vector[currentPosition] < search)
                {
                    left = currentPosition + 1;
                }

                if (vector[currentPosition] > search)
                {
                    right = currentPosition - 1;
                }
            }

            return -1;
        }