Wyszukiwanie binarne

    W jaki sposób szybko znajdować wartości w posortowanym zbiorze? Istnieje sprytny sposób na sprawne rozwiązywanie tego problemu - wyszukiwanie binarne. Poniższy artykuł umożliwi Wam zapoznanie się z tym potężnym i zarazem bardzo prostym algorytmem.

    Wyszukiwanie binarne pozwala na sprawne odszukiwanie wartości w posortowanych zbiorach. Jest to jednocześnie chyba jeden z najbardziej intuicyjnych algorytmów. Ludzie dość często korzystają ze zbliżonych do niego sposobów i zwykle nawet nie zdają sobie z tego sprawy. Czasami próbując odnaleźć swoje nazwisko czy też pesel na posegregowanej liście, staramy się "wstrzelić" w odpowiedni jej fragment, oszacować jakoś pozycję interesującego nas wpisu. Jest to strategia niezwykle podobna do tej, którą posługujemy się przy wyszukiwaniu binarnym.

    Aby wytworzyć pewną intiucję, przydatną przy dalszych rozważaniach, proponuję byście zagrali kilka razy w umieszczoną poniżej "grę". Wasz oponent wybiera na początku liczbę całkowitą z zakresu od do , a Wy staracie się ją odgadnąć, zadając jak najmniejszą ilość zapytań. Możecie jedynie sprawdzać, czy wytypowana przez Was liczba jest mniejsza, równa bądź większa, niż ta wybrana przez przeciwnika.
   
   

    Po kilku rozgrywkach można wyczuć, który sposób na typowanie kolejnych liczb pozwala na najszybsze odgadnięcie tej właściwej. Staramy się tak wybierać kandydatów, by niezależnie od odpowiedzi oponenta jak najbardziej zawężyć zbiór, w którym będziemy dalej szukać. Skoro przeciwnik mówi nam jedynie, czy podana przez nas wartość jest większa, mniejsza czy też równa właściwiej, to najlepiej zrobimy, gdy zapytamy go o wartość połowiącą przedział, w którym szukamy. Dzięki temu mamy pewność, że połowa liczb zostanie po jego odpowiedzi wyeliminowana z listy tych, które potencjalnie mogły zostać wybrane. Na przykład w chwili gdy dowiemy się, że oponent wytypował wartość większą niż , liczby od do całkowicie przestają nas interesować. Możemy być z siebie straszliwie zadowoleni - pozbyliśmy się przecież całkiem sporego zbioru.

    Dodatkowo dzięki tej taktyce jesteśmy odporni na nieuczciwych przeciwników! Nawet jeśli oponent będzie tak dobierał odpowiedzi na nasze pytania, byśmy musieli zadawać ich jak najwięcej, możemy zakończyć grę po najwyżej pięciu strzałach. Zauważ, że gdybyśmy wymieniali liczby po kolei (), to ilość pytań może wynieść nawet ...

    Wszystkie powyższe obserwacje sprawiają, że jesteśmy już tylko o krok od algorytmu wyszukiwania binarnego.