Wyszukiwanie binarne to algorytm znajdowania elementu w uporządkowanej, czyli posortowanej, tablicy. Jego główna zaleta to bardzo mała liczba porównań w porównaniu z wyszukiwaniem liniowym.
Warunek użycia
Aby zastosować wyszukiwanie binarne, dane muszą być posortowane. Jeśli tablica nie jest uporządkowana, algorytm nie będzie działał poprawnie.
Zasada działania
Algorytm sprawdza środkowy element tablicy:
- jeśli jest równy szukanej wartości, kończy działanie,
- jeśli szukana wartość jest mniejsza, dalsze wyszukiwanie odbywa się w lewej połowie,
- jeśli szukana wartość jest większa, dalsze wyszukiwanie odbywa się w prawej połowie.
Po każdym kroku liczba możliwych elementów zmniejsza się mniej więcej o połowę.
Złożoność
Złożoność czasowa wyszukiwania binarnego wynosi:
O(log n)- w typowym i pesymistycznym przypadku,O(1)- w najlepszym przypadku, gdy szukany element od razu znajduje się w środku.
Nie jest to więc algorytm o złożoności O(n²).
Przykład idei
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (tab[mid] == x) return mid;
if (tab[mid] < x) left = mid + 1;
else right = mid - 1;
}
Na egzaminie warto kojarzyć: wyszukiwanie binarne = tablica posortowana + dzielenie zakresu na połowy + O(log n).