Do czego służy algorytm wyszukiwania binarnego?

Aby skutecznie wyszukać element w posortowanej tablicy.

Istota polega na porównaniu poszukiwanego wartości z elementem w środku aktualnego zakresu wyszukiwania. Jeśli są równe, element został znaleziony. Jeśli poszukiwana wartość jest mniejsza, wyszukiwanie zawęża się do lewej połowy; jeśli jest większa, do prawej. Proces powtarza się, aż element zostanie znaleziony lub zakres wyszukiwania stanie się pusty.

Zaleta w porównaniu do wyszukiwania liniowego to logarytmiczna złożoność czasowa, O(log n), podczas gdy w przypadku liniowego jest to O(n). Czyni to wyszukiwanie znacznie szybszym dla dużych tablic.

Zastosowania:

• Wyszukiwanie w słownikach i bazach danych (indeksy).
• Algorytmy sortowania (np. w merge sort).
• Wyszukiwanie elementu korzenia równania.
• Wyszukiwanie w strukturach danych typu drzewa B.