Wyszukuje element w posortowanej tablicy przez wielokrotne dzielenie zakresu na połowy. O(log n).
Wyszukiwanie binarne (połówkowe) to algorytm znajdujący element w posortowanej tablicy w czasie logarytmicznym. To jedna z najważniejszych technik typu "dziel i zwyciężaj".
Warunek konieczny: tablica musi być posortowana. Bez tego algorytm nie działa poprawnie.
Idea: sprawdzamy element w środku zakresu poszukiwań. Jeżeli to szukana wartość – koniec. Jeżeli środkowy element jest większy od szukanego, kontynuujemy w lewej połowie. Jeżeli mniejszy – w prawej. Po każdym kroku zakres zmniejsza się o połowę.
Dlaczego logarytmicznie? Dla tablicy o rozmiarze 1 000 000 elementów potrzeba maksymalnie ok. 20 porównań (bo log₂(1 000 000) ≈ 20). Liniowe przeszukiwanie wymagałoby do miliona porównań.
Na maturze: typowe zadanie z analizą złożoności. Bardzo często pojawia się też w połączeniu z innymi algorytmami (np. sortowanie + wyszukiwanie binarne w jednym zadaniu).
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 // nie znaleziono
def wyszukiwanie_binarne(tablica, szukana):
"""Zwraca indeks szukanego elementu lub -1 gdy go 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 # nie znaleziono
def wyszukiwanie_binarne_rek(tablica, szukana, lewy=0, prawy=None):
"""Wersja rekurencyjna."""
if prawy is None:
prawy = len(tablica) - 1
if lewy > prawy:
return -1
srodek = (lewy + prawy) // 2
if tablica[srodek] == szukana:
return srodek
if tablica[srodek] < szukana:
return wyszukiwanie_binarne_rek(tablica, szukana, srodek + 1, prawy)
return wyszukiwanie_binarne_rek(tablica, szukana, lewy, srodek - 1)
# Przykład
posortowana = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(wyszukiwanie_binarne(posortowana, 7)) # 3
print(wyszukiwanie_binarne(posortowana, 4)) # -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;
if (t[srodek] < szukana) lewy = srodek + 1;
else prawy = srodek - 1;
}
return -1;
}
int main() {
vector<int> posortowana = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
cout << wyszukiwanie_binarne(posortowana, 7) << "\n"; // 3
cout << wyszukiwanie_binarne(posortowana, 4) << "\n"; // -1
}O(log n)O(1)O(log n)Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: