Zapisz się na listę

Wyszukiwanie binarne: jak działa krok po kroku

Wyszukiwanie binarne sprawdza element ze środka posortowanego przedziału i po jednym porównaniu odrzuca połowę danych — dlatego liczba kroków rośnie logarytmicznie, a nie liniowo.

Warunek wstępny jest jeden i jest bezwzględny: dane muszą być posortowane. Cały algorytm opiera się na wniosku, że jeżeli szukana wartość jest mniejsza od środkowej, to nie może leżeć w prawej połowie — a wniosek ten jest prawdziwy tylko dla ciągu uporządkowanego. Zadanie, które podaje tablicę nieposortowaną i pyta, czy można użyć wyszukiwania binarnego, pyta właśnie o to.

Przebieg jest krótki. Algorytm trzyma dwa indeksy wyznaczające przedział, w którym szukana wartość jeszcze może się znajdować, i w każdym kroku wylicza indeks środkowy. Porównanie ze środkiem ma trzy wyniki: trafienie kończy pracę, wartość mniejsza przesuwa prawy koniec przedziału przed środek, wartość większa przesuwa lewy koniec za środek. Przedział kurczy się co najmniej o połowę na krok.

Zysk widać przy porównaniu z przeszukiwaniem liniowym. Przeszukiwanie liniowe w najgorszym razie ogląda każdy element, więc liczba porównań rośnie tak jak długość tablicy. Wyszukiwanie binarne w każdym kroku odrzuca połowę, więc liczba kroków to tyle, ile razy da się długość podzielić na pół — czyli logarytm o podstawie dwa. Dla tablicy tysiąckrotnie dłuższej liniowe potrzebuje tysiąc razy więcej porównań, binarne — około dziesięciu więcej.

Najczęstszy błąd implementacyjny dotyczy warunku pętli i aktualizacji indeksów. Pętla ma działać, dopóki lewy indeks nie przekroczy prawego — użycie ostrej nierówności gubi przypadek przedziału jednoelementowego. Nowe końce przedziału muszą omijać sprawdzony środek; zapisanie ich jako samego środka zamiast sąsiedniego indeksu daje pętlę nieskończoną dla wartości, której w tablicy nie ma.

Wyszukiwanie binarne krok po kroku

  1. Sprawdź warunek wstępny

    Upewnij się, że ciąg jest uporządkowany. Jeżeli nie jest, algorytm nie daje błędnej odpowiedzi „czasem” — daje ją w sposób nieprzewidywalny, bo cała jego poprawność stoi na uporządkowaniu.

  2. Ustaw granice przedziału

    Lewy indeks na początek tablicy, prawy na jej koniec. Ten przedział jest jedynym miejscem, w którym szukana wartość może się jeszcze znajdować — i to zdanie pozostaje prawdziwe po każdym kroku.

  3. Wyznacz środek

    Indeks środkowy to część całkowita średniej z obu granic. W zapisie pseudokodowym dzielenie całkowite jest tu istotne: indeks musi być liczbą całkowitą, a zaokrąglenie w dół gwarantuje, że mieści się w przedziale.

  4. Porównaj wartość ze środka z szukaną

    Równość kończy pracę i zwraca indeks środkowy. Wartość środkowa większa od szukanej znaczy, że cała prawa część odpada; mniejsza — że odpada lewa.

  5. Zawęź przedział, omijając sprawdzony środek

    Odrzucając prawą część, ustaw prawy indeks na pozycję tuż przed środkiem. Odrzucając lewą — lewy indeks tuż za środkiem. Ustawienie granicy na sam środek zapętla algorytm, bo przedział przestaje się kurczyć.

  6. Powtarzaj, dopóki przedział nie jest pusty

    Pętla działa, dopóki lewy indeks nie jest większy od prawego. Moment, w którym go przekracza, oznacza, że przedział możliwych położeń jest pusty, czyli że wartości w tablicy nie ma.

  7. Zwróć wynik dla przypadku braku

    Po wyjściu z pętli zwróć umownie ustaloną wartość oznaczającą brak elementu. Zadanie zwykle wymaga, żeby ten przypadek był obsłużony jawnie, a nie pozostawiony bez odpowiedzi.

Gdzie najczęściej ginie punkt

  • Zapis algorytmu bez warunku uporządkowania danych, gdy polecenie pytało o założenia, przy których algorytm działa poprawnie.
  • Aktualizacja granicy na sam indeks środkowy zamiast sąsiedniego. Pętla przestaje się kończyć dla wartości spoza tablicy — to błąd wykrywany przy analizie przebiegu, nie przy czytaniu kodu.
  • Podanie złożoności bez wskazania, że liczba kroków wynika z połowienia przedziału. Punkt bywa za uzasadnienie, nie za symbol.
  • Pominięcie przypadku, w którym elementu nie ma. Algorytm ma zwrócić jawną informację o braku, a nie zakończyć się bez wartości.
Czego tu nie ma: treści zadań z arkuszy CKE, rozwiązań wzorcowych ani kluczy odpowiedzi. Ta strona opisuje własnymi słowami, czego dotyczy materiał i co sprawdzamy w Twoim rozwiązaniu. Zadania z arkuszy rozwiązuje się w aplikacji, po zalogowaniu.

Najczęstsze pytania

Jaka jest złożoność wyszukiwania binarnego?
Logarytmiczna, zapisywana jako O(log n). Każde porównanie ze środkiem odrzuca co najmniej połowę przedziału, więc kroków jest tyle, ile razy długość tablicy da się podzielić na pół. Przeszukiwanie liniowe w najgorszym razie ogląda każdy element. W zadaniu podaj też to uzasadnienie, bo punkt bywa za połowienie przedziału, a nie za sam symbol.
Czy wyszukiwanie binarne działa na nieposortowanej tablicy?
Nie. Algorytm odrzuca połowę danych po jednym porównaniu ze środkiem, a ten wniosek jest prawdziwy tylko dla ciągu uporządkowanego. Na tablicy nieposortowanej wynik staje się nieprzewidywalny: algorytm może nie znaleźć wartości, która w tablicy jest. Taką tablicę trzeba najpierw posortować albo przeszukać liniowo.
Jak zapisać wyszukiwanie binarne na kartce?
Zapisz pętlę na dwóch indeksach: lewy zaczyna od początku tablicy, prawy od końca. Pętla działa, dopóki lewy nie jest większy od prawego. Środek to część całkowita średniej z obu granic. Po porównaniu ustaw granicę tuż przed środkiem albo tuż za nim, nigdy na sam środek, a po wyjściu z pętli zwróć umówioną wartość oznaczającą brak elementu. Algorytm na kartce ocenia się za poszczególne elementy, więc każdy z nich musi być w zapisie widoczny.