Zagrajmy w prostą grę, która pozwoli Ci zrozumieć dlaczego różne algorytmy, zastosowane do rozwiązania tego samego problemu, mogą mieć tak bardzo różną skuteczność. Komputer wylosuje liczbę całkowitą od 1 do 16. Twoje zadanie polega na tym, żeby zgadnąć tą liczbę. Próbujesz tak długo aż zgadniesz, a komputer za każdym razem podpowiada Ci, czy Twoja liczba jest większa, czy mniejsza od tej, której szukasz:
Kiedy już zgadniesz, powiedz nam skąd wiedziałeś jaką liczbę wybrać w kolejnym kroku.
Może próbowałeś 1, potem 2, potem 3, potem 4 i tak dalej, aż trafiłeś na właściwą liczbę. Taką metodę nazywamy przeszukaniem liniowym., ponieważ zgadywałeś liczby po kolei. To działa. Ale jaka jest największa możliwa liczba prób jakich będziesz potrzebować? Jeśli komputer wybierze liczbę 16, będziesz potrzebować 16 prób. Z drugiej strony, jeśli masz szczęście, komputer wybierze liczbę 1 i trafisz w pierwszej próbie. A ile wynosi średnia liczba prób? Jeśli komputer wybiera z jednakowym prawdopodobieństwem każdą liczbę od 1 do 16 to średnio będziesz potrzebować 8 prób.
Czy można postąpić sprytniej niż zgadywać po kolei 1, 2, 3, 4, … ? Skoro komputer daje Ci informację czy zaproponowana przez Ciebie liczba jest większa, mniejsza czy równa tej wybranej przez komputer, możesz zacząć od 8. Jeśli liczba wybrana przez komputer jest mniejsza niż 8, możesz z góry wyeliminować wszystkie liczby od 8 do 16. Jeśli liczba wybrana przez komputer jest większa niż 8, możesz wyeliminować wszystkie liczby od 1 do 8. W obu przypadkach możesz wyeliminować połowę możliwości. W następnym kroku wyeliminujesz połowę pozostałych liczb. I tak dalej, za każdym razem eliminując połowę pozostałych liczb. To dzielenie na pół nazywamy przeszukiwaniem binarnym i niezależnie od tego jaką liczbę od 1 do 16 wybierze komputer tą metodą powinieneś zgadnąć prawidłową odpowiedź w nie więcej niż 4 próbach.
Spróbuj zgadnąć liczbę od 1 do 300. Nie powinieneś potrzebować więcej niż 9 prób.
Ile prób potrzebowałeś żeby zgadnąć tym razem? Dlaczego nigdy nie będziesz potrzebować więcej niż 9 prób? Potrafisz podać matematyczne wyjaśnienie?
Wrócimy jeszcze do przeszukiwania binarnego i zobaczymy jak można wykorzystać tą metodę aby skutecznie przeszukać tablicę zakodowaną w JavaScript. Na razie jednak zajmijmy się algorytmem rozwiązania bardziej złożonego problemu.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.
Ładowanie