Czego się nauczysz
Nauczysz się szukać w posortowanej liście przez połowienie zakresu. Każde sprawdzenie odrzuca połowę elementów, więc w milionie liczb wystarczy 20 kroków. Znajdziesz też pierwsze wystąpienie wartości i policzysz, ile liczb jest mniejszych od podanej.
Po co ci to na maturze
Wyszukiwanie binarne jest w podstawie programowej, a zadania na analizę pytają, ile kroków wykona albo co zwróci dla podanej listy. Przydaje się też, gdy w uporządkowanych danych trzeba szybko odpowiedzieć na wiele pytań.
Etapy lekcji
Spis lekcji
Teoria
5 rozdziałówNie zaczęte- 1.1Połowa za połowąW posortowanej liście jedno sprawdzenie środka odrzuca połowę elementów.
- 1.2Lewy, prawy i środekLewy i prawy to granice kawałka listy, w którym jeszcze szukasz. Środek leży pośrodku między nimi.
- 1.3Ile krokówDwa razy więcej danych to tylko jeden krok więcej. To czas logarytmiczny.
- 1.4Granica: pierwsze wystąpienie i liczby mniejszeZamiast szukać samej liczby, szukasz miejsca, w którym kończą się liczby od niej mniejsze.
- 1.5PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.