Інформатика · Двійковий пошук
Як знайти одне ім’я з мільйона за 20 кроків?
Що ви побачите
У телефонному довіднику мільйон імен, за абеткою. Перевірка по одному може забрати мільйон поглядів. Чи можна швидше? Розгорніть його рівно посередині. Потрібне ім'я далі, тож уся перша половина відпадає. Лишається пів мільйона. Розгорніть середину того, що лишилося, і знову поділіть навпіл. І ще раз. Кожен погляд відкидає половину того, що лишилося. Двадцять поділів навпіл зводять мільйон до одного, бо два в двадцятому степені трохи більше за мільйон. Мільярд імен? Лише на десять поглядів більше.
