Wyszukiwanie binarne – algorytm, który musisz znać na Olimpiadzie Informatycznej!

Wyszukiwanie binarne to jedno z najważniejszych narzędzi w arsenale każdego Olimpijczyka na Olimpiadzie Informatycznej, czy Olimpiadzie Informatycznej Juniorów. Jest nie tylko przydatne samo w sobie, ale stanowi także podstawę wielu bardziej zaawansowanych algorytmów. W tym artykule wyjaśnimy, na czym polega jego działanie, pokażemy, jak je zaimplementować oraz przeanalizujemy przykłady jego zastosowania. Zwrócimy także uwagę na to, jakie warunki musi spełniać problem, aby można było skutecznie zastosować wyszukiwanie binarne.

Wyszukiwanie binarne – motywacja

Zacznijmy od prostego przykładu – gry w zgadywanie liczby. Jedna osoba wymyśla liczbę z przedziału od 1 do 100, a druga próbuje ją odgadnąć. Przy każdej próbie zgadujący otrzymuje informację zwrotną: ,,za mała’’, ,,za duża’’ lub ,,dobrze”. Choć gra może wydawać się prosta, a nawet losowa, to w rzeczywistości pozwala na zastosowanie sprytnej taktyki, która znacznie przyspiesza znalezienie poprawnej odpowiedzi.

Zastanówmy się najpierw, jakie strategie możemy przyjąć, żeby odgadnąć liczbę w jak najmniejszej ilości prób. Najprostszą metodą, którą wielu z nas kiedyś użyło, jest zgadywanie losowych liczb do momentu, aż trafimy na właściwą. Inną opcją jest zgadywanie kolejnych wartości po kolei, zaczynając od początku lub końca przedziału. Obie te strategie są jednak nieoptymalne, w najgorszym przypadku możemy odgadnąć wszystkie możliwe liczby, zanim dojdziemy do tej poprawnej. Zauważmy przy tym, że oba te podejścia nie wykorzystują w żaden sposób informacji o tym, czy szukana przez nas liczba jest większa czy mniejsza od zgadywanej.

Jak zatem poprawić nasz wynik? W momencie zgadywania jakiejś liczby, na przykład ,,10’’, mogą wydarzyć się dwie rzeczy:

• Przy odpowiedzi ,,za mała’’ dowiadujemy się, że szukana liczba jest większa od 10. Co jednak dodatkowo możemy wywnioskować, to to, że na pewno nie będzie to też żadna z liczb od 1 do 10.
• Analogicznie, przy odpowiedzi ,,za duża”, możemy wyeliminować wszystkie liczby, tym razem większe od 10. Teraz jednak przedział [11, 100] zawiera w sobie dużo więcej liczb, co daje nam zaledwie kilka możliwych odpowiedzi.

Różne liczby mogą nam dać różny rezultat i ,,obciąć’’ więcej lub mniej możliwości. Niestety wybór jednak nie jest taki prosty, ponieważ prawdopodobieństwo tych rezultatów jest różne. Wracając do naszego przykładu, odpowiedź ,,za mała’’ jest dużo bardziej prawdopodobna niż druga. Gdybyśmy zawsze zgadywali liczbę z jednej strony przedziału, np. 10, to najczęściej dostawalibyśmy tą odpowiedź i eliminowali tylko niewielką część możliwości. Dlatego potrzebujemy lepszej strategii, która maksymalnie skraca przedział po każdej próbie – niezależnie od wyniku.

Działanie

Wyszukiwanie binarne, czyli algorytm, który pomoże nam rozwiązać problem postawiony wyżej, działa zgodnie z jedną prostą zasadą. Dopóki nie zgadniemy poprawnej liczby, zawsze celujemy dokładnie w środek aktualnego przedziału liczb, które są możliwym wynikiem. 

W ten sposób, niezależnie od tego, jaką odpowiedź dostaniemy, zawsze eliminujemy dokładnie połowę możliwości. To właśnie sprawia, że wyszukiwanie binarne jest tak skuteczne – skraca przestrzeń rozwiązań najszybciej jak to możliwe. W analizie algorytmów szczególnie interesuje nas najgorszy możliwy przypadek (tzw. pesymistyczny scenariusz), a wyszukiwanie binarne zapewnia, że nawet wtedy liczba kroków czy strzałów rośnie bardzo wolno – logarytmicznie względem rozmiaru przedziału.

Poniżej przedstawiamy przykładową implementację algorytmu wyszukiwania binarnego w języku C++. W kodzie jest dodatkowa funkcja “czySzukana()”, która zwraca string z odpowiedzią drugiego gracza.

Jak widać, implementacja algorytmu wyszukiwania binarnego jest krótka i całkiem prosta. Warto ją zapamiętać, ponieważ różnice między implementacjami do konkretnych zadań będą niewielkie. Ze względu na to, że w każdym kroku pętli ilość możliwych wyników zmniejsza się o połowę, potrzebujemy maksymalnie logarytmiczną ilość obrotów. Także proste oszacowanie daje nam złożoność O(log n).

Wyszukiwanie binarne – uwagi

Przedstawiony powyżej algorytm jest bardzo uniwersalny i często może pomóc w zoptymalizowaniu wielu rozwiązań. Istnieje też wiele innych przykładów z życia, w których można go użyć. Następnym razem, gdy zapomnicie zakładki w książce, lub będziecie szukać słowa w słowniku, możecie przypomnieć sobie ten artykuł. Trzeba jednak wiedzieć, jakie zadania nadają się do wyszukiwania binarnego oraz jakie warunki muszą zostać spełnione, żeby móc zastosować tę technikę.

1. Zadanie musi szukać wartości. To może być oczywisty warunek, ale niemniej jednak jest ważny. Można to też traktować jako pewnego rodzaju sugestię. Gdy polecenie wymaga znalezienie jednej konkretnej wartości, często może się okazać, że jest to idealne zadanie dla wyszukiwania binarnego.
2. Dane muszą być możliwe do posortowania. Tak jak opisywaliśmy wcześniej, wyszukiwanie binarne polega w pełni na informacji ,,mniejszy’’ lub ,,większy’’. Ta informacja jednak jest dostępna tylko w zbiorach monotonicznych. Gdyby słowa w słowniku nie były posortowane, zajrzenie na jakąś stronę nie dałoby nam żadnej dodatkowej wiedzy. Często w zadaniu możemy sobie sami posortować tablicę, jednak należy zwracać szczególną uwagę, czy dane tworzą jakiś porządek, oraz czy obecna kolejność nie jest istotna dla zadania.

Częstym archetypem pytania, dla którego oczekiwane jest wyszukiwanie binarne, jest ,,Znajdź najmniejszą wartość X, dla której spełniony jest warunek Y’’. W tym wypadku dodatkową własnością, której potrzebujemy, jest to, że jeżeli dla jakiejś liczby x warunek nie jest prawdziwy, to dla każdej mniejszej też nie będzie.

Wstęp do wyszukiwania binarnego: wiedza w pigułce!

Gratulacje! Teraz już znasz wyszukiwanie binarne, jeden z najbardziej kluczowych algorytmów. Choć jest to jedna z prostszych technik, to bardzo często pojawia się jako część rozwiązania, lub dodatkowa wymagana optymalizacja. Dlatego znajomość tego sposobu jest niesamowicie istotna dla wszystkich Olimpijczyków, niezależnie od tego, czy startujesz w Olimpiadzie Informatycznej, czy Olimpiadzie Informatycznej Juniorów.

Zakończymy ten artykuł z jedną małą radą. Zaletą tego algorytmu jest między innymi jego elastyczność i możliwość dostosowania do zadania. Jest to jednak również jego trudnością – każde zadanie będzie miało odrobinę inną implementację algorytmu. Dlatego warto przećwiczyć sobie jego użycie w domu na kilku zadaniach. Takie doświadczenie może okazać się kluczowe przy rozwiązywaniu zadań na samych zawodach.

Nie czekaj – dołącz do Indeksu w Kieszeni i rozpocznij solidne:

• przygotowanie do Olimpiady Licealnej
• przygotowanie do Olimpiady dla Szkół Podstawowych