Szuka liczby w posortowanej tablicy, odrzucając za każdym razem połowę. O(log n).
Wyszukiwanie binarne to szybki sposób na znalezienie liczby w tablicy – ale pod jednym warunkiem: tablica musi być posortowana. Zamiast sprawdzać liczby po kolei, za każdym razem odrzucasz od razu całą połowę.
Jak to działa? Patrzysz na liczbę w samym środku. Jeśli to ta, której szukasz – gotowe. Jeśli środkowa liczba jest za duża, szukasz dalej tylko w lewej połowie (tam są mniejsze). Jeśli za mała – tylko w prawej. I tak w kółko: każdy krok wyrzuca połowę tego, co zostało do sprawdzenia.
Dlaczego takie szybkie? Bo połowienie schodzi błyskawicznie. W tablicy miliona liczb wystarczy około 20 kroków, żeby dojść do jednej. Zwykłe sprawdzanie po kolei mogłoby wymagać nawet miliona porównań.
Uwaga na warunek: jeśli tablica nie jest posortowana, wyszukiwanie binarne daje błędne wyniki – bo „skręcanie" w lewo lub w prawo ma sens tylko wtedy, gdy mniejsze liczby są z jednej strony, a większe z drugiej.
Na maturze: klasyk. Często trzeba policzyć, ile porównań zrobi algorytm dla podanej tablicy, albo połączyć go z sortowaniem w jednym zadaniu.
Prześledź, jak algorytm szuka liczby, za każdym razem odrzucając połowę tablicy. Sprawdzana środkowa liczba jest podświetlona, odrzucone części szarzeją, a znaleziona liczba robi się zielona.
Szukamy liczby: 23
Naciśnij „Krok", aby sprawdzić środkową liczbę, albo „Auto".
funkcja wyszukaj_binarnie(T, szukana): lewy ← 0 prawy ← długość(T) - 1 dopóki lewy ≤ prawy: środek ← (lewy + prawy) div 2 jeżeli T[środek] = szukana: zwróć środek // znaleziono jeżeli T[środek] < szukana: lewy ← środek + 1 // szukamy w prawej połowie w przeciwnym razie: prawy ← środek - 1 // szukamy w lewej połowie zwróć -1 // liczby nie ma w tablicy
def wyszukiwanie_binarne(tablica, szukana):
"""Zwraca indeks szukanej liczby albo -1, gdy jej nie ma.
UWAGA: tablica musi być posortowana rosnąco."""
lewy = 0
prawy = len(tablica) - 1
while lewy <= prawy:
srodek = (lewy + prawy) // 2
if tablica[srodek] == szukana:
return srodek # znaleziono
elif tablica[srodek] < szukana:
lewy = srodek + 1 # szukamy w prawej połowie
else:
prawy = srodek - 1 # szukamy w lewej połowie
return -1 # liczby nie ma
# Przykład użycia
posortowana = [2, 5, 8, 12, 16, 23, 38, 56]
print(wyszukiwanie_binarne(posortowana, 23)) # 5
print(wyszukiwanie_binarne(posortowana, 100)) # -1#include <vector>
#include <iostream>
using namespace std;
int wyszukiwanie_binarne(const vector<int>& t, int szukana) {
int lewy = 0, prawy = (int)t.size() - 1;
while (lewy <= prawy) {
int srodek = (lewy + prawy) / 2;
if (t[srodek] == szukana) return srodek; // znaleziono
if (t[srodek] < szukana) lewy = srodek + 1; // prawa polowa
else prawy = srodek - 1; // lewa polowa
}
return -1;
}
int main() {
vector<int> posortowana = {2, 5, 8, 12, 16, 23, 38, 56};
cout << wyszukiwanie_binarne(posortowana, 23) << "\n"; // 5
cout << wyszukiwanie_binarne(posortowana, 100) << "\n"; // -1
}Bo cała sztuczka polega na tym, że jak środkowa liczba jest za duża, to wszystkie liczby na prawo od niej też są za duże i można je wyrzucić naraz. To działa tylko wtedy, gdy liczby są ułożone po kolei. W nieposortowanej tablicy „skręcanie" w lewo lub w prawo nic nie znaczy.
Zwykle -1. Dzieje się tak, gdy zakres poszukiwań się skurczy do zera, czyli lewy koniec przeskoczy prawy (lewy > prawy). Wtedy wiadomo już na pewno, że szukanej liczby w tablicy nie ma.
Przeszukiwanie po kolei sprawdza liczbę po liczbie, więc w najgorszym razie ogląda całą tablicę – to O(n). Wyszukiwanie binarne za każdym razem odrzuca połowę, więc kroków jest tylko O(log n). Cena to warunek: tablica musi być posortowana.
Mniej więcej tyle, ile razy da się n podzielić na pół, czyli około log₂ n. Dla 1000 liczb to około 10 porównań, dla miliona – około 20.
Prześledź wyszukiwanie binarne w tablicy [2, 5, 8, 12, 16, 23, 38, 56] (8 liczb) i wpisz odpowiedzi, potem kliknij Sprawdź.
Najpierw algorytm patrzy zawsze na liczbę ze środka. Dla tej tablicy pierwsza sprawdzana liczba to (element o indeksie 3).
Szukając liczby 23, algorytm zrobi porównania. Szukając 8 – porównania. Szukając 100, której w tablicy nie ma – porównania.
Warunek, bez którego ten algorytm nie zadziała: tablica musi być .
Uzupełnij, ile najwyżej razy trzeba podzielić tablicę na pół, żeby zostać z jedną liczbą:
| Liczba elementów | Najwyżej połówień |
|---|---|
| 8 | |
| 16 | |
| 1024 |
O(log n)O(1)Czasowa O(log n). Każdy krok wyrzuca połowę liczb, więc kroków jest tyle, ile razy da się podzielić n na pół. Pamięć O(1) w wersji z pętlą – trzymasz tylko trzy liczby: lewy koniec, prawy koniec i środek. Wersja z rekurencją zużywa O(log n) pamięci na wywołania funkcji.
Do tego hasła nie mamy jeszcze przypisanych pojedynczych zadań. Cały spis zadań maturalnych z tego działu jest tutaj:
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: