Какое максимальное количество операций в бинарном поиске?

Question

[Никита Стечкин]

Количество операций можно высчитать,например,по формуле log n, но когда я проверяю это на листе, то получается на 1 больше. Если взять 8, то максимальное кол-во операций по формуле будет 3,допустим, я загадал 8, получается:

-4?
-Больше.
-6?
-Больше.
-7?
-Больше.
-8?
Да.
И число 8 удалось угадать только с 4 попытки. Почему не подходит формула?

Answer 1

[Сергей Соколов]

С краями ошиблись: 3 бита (3 вопроса) — это числа от 0 до 7.
Каждым вопросом уточняется бит, от старших к младшим:

0  000
1  001
2  010
3  011
4  100 - четыре?  - больше (старший бит 1xx )
5  101
6  110 - шесть? - больше ( 11x )
7  111 - семь – ага

Comments

[Никита Стечкин]

Спасибо за ваш ответ,но что если теперь я загадаю число 0?Получается:

- 4?
- Меньше.
- 2?
- Меньше.
- 1?
-Меньше.
0-?
-Да.
Т.е. снова 4 или 0 нельзя загадывать, можно только те, которые 0 < num < 8?

[Сергей Соколов]

Никита Стечкин, каждый вопрос уточняет очередной бит. Задуманное число тоже запишите битами. 0: 0b000

бит 2: 0b100 = 4 ? — меньше (т.е. этот бит 0, число 0b0xx)
бит 1: 0b010 = 2 ? — меньше (0b00x)
бит 0: 0b001 = 1 ? – меньше – ответ 0b000

Ответы могут быть "больше", "меньше" и "угадал число".

[Сергей Соколов]

Ещё пример, задумали 5. В двоичной это 101.
Договорились, что число от 0 до 7 (в двоичной до 111). Наибольший значимый бит (MSB) 2-й (считая от 0, 1, 2).
Узнаём про него, про 2-й. Берём число в двоичной 100, это 4.
– Это 4 ? –  больше (значит, бит включён), число в двоичной 1xx

Узнаем про следующий бит, проверим число 110
– это 6 ? – меньше. Значит, этот бит 0. Итого известно 10x

Остаётся младший бит. Ставим и ему 1 и спрашиваем про 101
– это 5 ? – угадали.

[Никита Стечкин]

Сергей Соколов, понял, спасибо

Answer 2

[Mercury13]

ceil(log₂(n + 1))

Поскольку ответов на каждый конкретный вопрос возможны три штуки (больше/меньше/угадал), тупая оценка количеством битов невозможна, надо учитывать зависимости между этими ответами.

Доказательство.
Докажем обратное: за k шагов можно угадать 2^k−1 чисел.

БАЗА. 1 угадывается с первого раза. 2 с первого раза уже не угадаешь.

ШАГ. k → k+1. Другими словами, нам известно, что 2^k−1 угадать можно, а 2^k уже нельзя.
Берём центральное, и остаётся 2^k−1 слева и 2^k−1 справа. → n = 2·(2^k−1)+1 = 2^k+1−1
Если n = 2^k+1 или больше, хоть в одной половинке будет 2^k, что, по предположению индукции, невозможно.

Comments

[Василий Банников]

2 с первого раза уже не угадаешь.

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

[Mercury13]

Василий Банников, Но нужно ещё этот результат озвучить и получить ответ «Угадал».

[Wataru]

Василий Банников, это если вы точно знаете, что число в массиве есть. Тогда ceil(log n). Если же возможен ответ - не нашлось - то надо + 1 под логарифмом.

[Никита Стечкин]

спасибо за помощь