Грокаем а Иллюстрированное пособие для программистов и любопытствующих

При бинарном поиске каждый раз исключается половина чисел
Какое бы число я ни задумал, вы гарантированно сможете угадать его не бо­лее чем за 7 попыток, потому что с каждой попыткой исключается половина оставшихся чисел!
Предположим, вы ищете слово в словаре с 240 000 словами. Как вы думаете, сколько попыток вам понадобится в худшем случае?
ПРОСТОЙ ПОИСК: ШАГОВ
БИНАРНЫЙ ПОИСК: ШАГОВ
П
120к|~* |60К| —* 130к] -»)Т5К~| —»[TTskI->|3?50l


С
Гз*|-»огы ^г I -»1 ^


я


Ш:

ри простом поиске может потребоваться 240 000 попыток, если искомое слово находится на самой последней позиции в книге. С каждым шагом бинарного поиска количество слов сокращается вдвое, пока не останется только одно слово.
16 ШАГОВ
Итак, бинарный поиск потребует 18 шагов — заметная разница! В об­щем случае для списка из п элементов бинарный поиск выполняется за log₂w шагов, тогда как простой поиск будет выполнен за п шагов.
ЛОГАРИФМЫ
Возможно, вы уже забыли, что такое логарифм, но наверняка помни­те, что такое возведение в степень. log₁₀100 по сути означает, сколько раз нужно перемножить 10, чтобы получить 100. Правильный от­вет — 2: 10 х 10. Итак, log₁₀100 = 2. Логарифм по смыслу противопо­ложен возведению в степень.
“100 log,J0$ ^s2
2 “8 1од₄8
2* - 16 logj6 =4
2 ~32 1.0^32 * 5