Поиск половинным делением

Возьмём для примера игру в угадывание целого числа в определенном диапазоне. Например, от 1 до 128. Один играющий загадывает число, вто­рой пытается его угадать, задавая вопросы, на которые ответом может быть «да» или «нет». Ключом поиска в этом случае является число, а кри­терием поиска – совпадение числа, задуманного первым игроком, с чис­лом, называемым вторым игроком.

Если вопросы задавать такие: «Число равно единице?». Ответ: «Нет». Вопрос: «Число равно двум?» и т.д., то это будет последовательным пере­бор. Среднее число вопросов при многократном повторении игры с загады­ванием разных чисел из данного диапазона будет равно 12/2 = 64.

Такой метод поиска называется методом половинного деления. Согласно этому методу, вопросы надо задавать так, чтобы каждый ответ уменьшал число неизвестных в два раза.

Так же надо искать и одно число из 128. Первый вопрос: «Число меньше 65?» – «Да! – «Число больше 32?» – «Нет!» и т. д. Любое число уга­дывается максимум за 7 вопросов. Это связано с тем, что 128 = 2⁷. Снова работает главная формула информатики.

Метод половинного деления для упорядоченного набора данных работа­ет гораздо быстрее (в среднем), чем метод последовательного перебора.

На рисунке наглядно показан процесс поиска (угадывания) числа «3» из диапазона целых чисел от 1 до 8.

Если максимальное число диапазона N не равно целой степени двойки, то оптимальное количество вопросов не будет постоянной величиной, а бу­дет равно одному из двух значений: X или Х+1, где

2^Х < N < 2^X+1

Например, если тело ищется в диапазоне от 1 до 7 то его можно уга­дать за 2 или 3 вопроса, поскольку

2² < 7 < 2³.

Число из диапазона от 1 до 200 можно угадать за 7 или 8 вопросов, по­скольку

2⁷ < 200 < 2⁸.

Проверьте эти утверждения экспериментально.

Половинным делением можно искать, например, нужную страницу в толстой книге: открыть книгу посередине, понять, в какой из половин на­ходится искомая страница. Затем открыть середину этой половины и т. д.

Набор данных может быть упорядочен не только по числовому ключу. Другой вариант упорядочения – по алфавиту. Половинным делением можно осуществлять поиск в орфографическом словаре или в словаре пе­реводов слов с иностранного языка.