Wyszukiwanie binarne: jak wytłumaczyć je dziecku
Wyszukiwanie binarne na przykładzie gry w zgadywanie liczby: dlaczego wystarczy 7 pytań na 100 liczb, jak wygląda algorytm krok po kroku i jakie błędy popełniają dzieci.
Aktualizacja:
Wyszukiwanie binarne to jeden z pierwszych algorytmów, przy których dziecko widzi, że sprytny sposób bije cierpliwość. Najłatwiej zacząć od gry.
Gra: zgadnij liczbę
Pomyśl liczbę od 1 do 100. Dziecko zgaduje, a ty odpowiadasz tylko „za mało”, „za dużo” albo „trafione”.
Na początku dzieci strzelają na ślepo albo pytają po kolei: 1, 2, 3… Zapytaj wtedy, od której liczby warto zacząć, żeby na pewno odpadło jak najwięcej. Odpowiedź to środek: 50.
Dlaczego środek
Po pytaniu o 50 zostaje połowa liczb, niezależnie od odpowiedzi. Po następnym pytaniu ćwierć. Zakres maleje tak: 100, 50, 25, 13, 7, 4, 2, 1. To siedem pytań. Przy tysiącu liczb wystarczy dziesięć, a przy milionie dwadzieścia.
Pytając po kolei, w najgorszym razie trzeba by stu pytań.
Algorytm krok po kroku
- Zapamiętaj dwa końce zakresu:
lewyiprawy. - Policz środek.
- Jeśli środek to szukana liczba, koniec.
- Jeśli jest za mały, przesuń
lewytuż za środek. Jeśli za duży, przesuńprawytuż przed środek. - Wróć do kroku 2.
To pętla z decyzją w środku i dwiema zmiennymi, które się do siebie zbliżają.
Gdzie to się przydaje
- Szukanie słowa w słowniku papierowym: otwierasz w środku i wiesz, w którą stronę iść.
- Szukanie strony w książce.
- Zgadywanie wzrostu, ceny, daty.
Warunek jest jeden: dane muszą być uporządkowane.
Typowe błędy
- Zakres się nie zmniejsza. Jeśli
lewyprzesuwa się na środek, a nie za środek, pętla może kręcić się bez końca. - Dane nie są posortowane. Wtedy algorytm odrzuca połowę, w której mogła być odpowiedź.
- Szukanej liczby nie ma. Pętla musi się skończyć, gdy
lewyminieprawy.
W Looponi
Wyszukiwanie binarne jest jednym z algorytmów na ścieżce dla klas 7–8. Uczeń układa je jako schemat blokowy, obstawia, ile obrotów zrobi pętla, i patrzy, jak końce zakresu zbliżają się do siebie przy każdym kroku.
Najczęstsze pytania
Co to jest wyszukiwanie binarne?
To sposób szukania w uporządkowanych danych, w którym po każdym pytaniu odrzuca się połowę możliwości. Sprawdzamy środek i idziemy w lewo albo w prawo.
Ile pytań trzeba, żeby zgadnąć liczbę od 1 do 100?
Najwyżej 7. Każde pytanie zmniejsza zakres o połowę: 100, 50, 25, 13, 7, 4, 2, 1.
Dlaczego dane muszą być uporządkowane?
Bo tylko wtedy odpowiedź „za mało” albo „za dużo” mówi, którą połowę można odrzucić. W pomieszanych danych trzeba sprawdzać po kolei.
Od jakiego wieku można tego uczyć?
Grę w zgadywanie liczby rozumie już ośmiolatek. Sam algorytm ze zmiennymi warto wprowadzić około 12–13 lat.