oleg-glushko / erratas Goto Github PK

Олег, здравствуйте!

Приятно было увидеть ваш код в репозитории книги "Грокаем алгоритмы", но не согласен с вашим утверждением "Для 8 чисел нам, на самом деле, в худшем случае понадобится проверить 4 числа." :)

На самом деле, достаточно 3х, учитывая условие игры:

• en: You have to try to guess my number in the fewest tries possible. With every guess, I’ll tell you if your guess is too low, too high, or correct.

• ru: Вы должны отгадать мое число, использовав как можно меньше попыток. При каждой попытке я буду давать один из трех ответов: «мало», «много» или «угадал».

По алгоритму, мы выбираем границы, называем среднее число и, при необходимости, двигаем одну из границ, чтобы назвать следующее среднее. Поэтому всегда наступает момент, когда остаётся лишь пара чисел - среднее и не-среднее.

Рассмотрим простой случай - отгадывание любого числа из списка "0 1 2". Достаточно одного вопроса: по алгоритму мы называем среднее число - "1" -> либо мы угадали, либо из ответа больше / меньше становится понятно, что было загадано и снова спрашивать уже не нужно.

Далее рассмотрим список "0 1 2 3" - четыре числа, в теории достаточно 2х вопросов в худшем случае. Действительно, первое среднее будет "1", а худший случай - дальний от среднего - "3":

1. вопрос: "это 1?"

   ответ: "больше!" -> сдвинули нижнюю границу до "2", посчитали среднее - "2"

2. вопрос: "это 2?"
   ответ: "больше!" -> ясно: методом исключения это оставшееся "3"

Грокал двоичный поиск здесь:

• 01_BinarySearch.psm1 - непосредственно функции - моя и ваша, модифицированная возвращать кол-во спрошенных чисел

• 01_BinarySearch.ps1 - тесты - $lim = 7 для проверки каждого числа из списка 0..7