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

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

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