Введение в бинарный поиск

Предположим, вы ищете человека по имени “Эльвира” в огромном телефонном справочнике. Он может состоять из 100 страниц, и было бы утомительно изучать каждую из них с самого начала линейным способом, пока вы не найдете девушку с нужным вам именем. К счастью, имена в справочнике расположены в алфавитном порядке  —  это большой плюс.

Представьте, что вы открываете справочник на середине. Вы смотрите на страницу и видите имена, начинающиеся на “Н”. Зная, что буква “Э” идет после “Н”, вы разрываете справочник пополам и выбрасываете ту его половину, которая содержит имена до буквы “Н”. У вас в руках осталась книга меньшего размера.

Затем вы снова открываете справочник на середине. Теперь вы видите имена, начинающиеся на букву “С”. Вы снова разрываете справочник пополам и выбрасываете ту половину, которая содержит имена до “С”.

Продолжайте повторять эту процедуру, и вскоре вы окажетесь на страницах с буквой “Э”.