Algorytm wyszukiwania binarnego z PRZYKŁADEM

Zanim omówimy wyszukiwanie binarne, wyjaśnijmy, czym jest wyszukiwanie.

Co to jest wyszukiwanie?

Wyszukiwanie to narzędzie umożliwiające użytkownikowi wyszukiwanie dokumentów, plików, multimediów i innych typów danych przechowywanych w bazie danych. Wyszukiwanie działa na prostej zasadzie dopasowywania kryteriów do rekordów i wyświetlania ich użytkownikowi. W ten sposób działa najbardziej podstawowa funkcja wyszukiwania.

Co to jest wyszukiwanie binarne?

Wyszukiwanie binarne to zaawansowany typ algorytmu wyszukiwania, który wyszukuje i pobiera dane z posortowanej listy elementów. Jego podstawowa zasada działania polega na dzieleniu danych z listy na pół, aż do momentu znalezienia i wyświetlenia użytkownikowi żądanej wartości w wynikach wyszukiwania. Wyszukiwanie binarne jest powszechnie znane jako wyszukiwanie w połowie przedziału lub wyszukiwanie logarytmiczne.

Jak działa wyszukiwanie binarne?

Wyszukiwanie binarne działa w następujący sposób:

• Proces wyszukiwania rozpoczyna się od zlokalizowania środkowego elementu posortowanej tablicy danych.
• Następnie wartość klucza jest porównywana z elementem.
• Jeśli wartość klucza jest mniejsza niż środkowy element, wówczas wyszukiwanie analizuje wyższe wartości dla środkowego elementu w celu porównania i dopasowania.
• Jeśli wartość klucza jest większa niż wartość środkowego elementu, wówczas wyszukiwanie analizuje niższe wartości środkowego elementu w celu porównania i dopasowania.

Algorytm wyszukiwania binarnego (pseudokod)

Przeszukiwanie binarne można zapisać jako krótką, iteracyjną procedurę. Utrzymuje ona dwa wskaźniki, niski i wysoki, i zawęża zakres, aż do znalezienia celu lub opróżnienia zakresu.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

Procedura zwraca indeks celu w przypadku powodzenia oraz -1, gdy wartość nie jest obecna. Ponieważ zakres zmniejsza się o połowę przy każdym przejściu, pętla wykonuje się maksymalnie log₂(n) razy.

Przykładowe wyszukiwanie binarne

Przyjrzyjmy się przykładowi słownika. Jeśli trzeba znaleźć określone słowo, nikt nie przechodzi przez każde słowo w sposób sekwencyjny, ale losowo lokalizuje najbliższe słowa, aby wyszukać wymagane słowo.

Powyższy obraz ilustruje następujące zjawisko:

1. Masz tablicę składającą się z 10 cyfr i należy znaleźć element 59.
2. Wszystkie elementy są oznaczone indeksem od 0 do 9. Teraz obliczany jest środek tablicy. Aby to zrobić, należy wziąć skrajne lewe i prawe wartości indeksu i podzielić je przez 2. Wynik to 4.5, ale bierzemy wartość dolną. Zatem środek to 4.
3. Algorytm usuwa wszystkie elementy ze środka (4) do najniższej granicy, ponieważ 59 jest większe niż 24, a teraz tablica pozostaje tylko z 5 elementami.
4. Teraz 59 jest większe od 45 i mniejsze od 63. Wartość środkowa wynosi 7. W związku z tym wartość indeksu po prawej stronie staje się wartością środkową − 1, co równa się 6, a wartość indeksu po lewej stronie pozostaje taka sama jak poprzednio, czyli 5.
5. W tym momencie wiesz, że 59 następuje po 45. Zatem lewy indeks, który wynosi 5, również staje się środkowy.
6. Te iteracje są kontynuowane, dopóki tablica nie zostanie zredukowana do tylko jednego elementu lub znaleziony element nie stanie się środkiem tablicy.

2 przykład

Przyjrzyjmy się poniższemu przykładowi, aby zrozumieć działanie wyszukiwania binarnego.

1. Masz tablicę posortowanych wartości od 2 do 20 i musisz zlokalizować 18.
2. Średnia dolnej i górnej granicy wynosi (l + r) / 2 = 4. Szukana wartość jest większa od wartości środkowej, która wynosi 4.
3. Wartości tablicy mniejsze od wartości środkowej są pomijane podczas wyszukiwania, a wyszukiwane są wartości większe od wartości środkowej 4.
4. Jest to powtarzający się proces dzielenia, dopóki nie zostanie znaleziony właściwy element do przeszukania.

Dlaczego potrzebujemy wyszukiwania binarnego?

Poniższe powody sprawiają, że wyszukiwanie binarne jest lepszym wyborem jako algorytm wyszukiwania:

• Wyszukiwanie binarne działa efektywnie w przypadku posortowanych danych bez względu na ich rozmiar.
• Zamiast przeprowadzać wyszukiwanie poprzez sekwencyjne przeglądanie danych, algorytm binarny losowo uzyskuje dostęp do danych, aby znaleźć wymagany element. Dzięki temu cykle wyszukiwania są krótsze i dokładniejsze.
• W przypadku wyszukiwania binarnego porównania posortowanych danych opierają się na zasadzie porządkowania, a nie na porównaniach równości, które są wolniejsze i przeważnie niedokładne.
• Po każdym cyklu wyszukiwania algorytm dzieli rozmiar tablicy na połowę; w związku z tym w następnej iteracji będzie działał tylko na pozostałej połowie tablicy.

Zapoznaj się z naszym kolejnym samouczkiem na temat Wyszukiwanie liniowe: Python, C++ Przykład.

Wyszukiwanie binarne a wyszukiwanie liniowe

Przeszukiwanie binarne i liniowe to dwie najpopularniejsze metody wyszukiwania wartości w zbiorze. Poniższa tabela pokazuje, czym się różnią:

Krótko mówiąc, wyszukiwanie binarne jest znacznie szybsze w przypadku dużych, posortowanych danych, natomiast wyszukiwanie liniowe jest prostsze i stanowi jedyną opcję, gdy dane nie są posortowane.

FAQ