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

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

-4?
-Больше.
-6?
-Больше.
-7?
-Больше.
-8?
Да.
И число 8 удалось угадать только с 4 попытки. Почему не подходит формула?
  • Вопрос задан
  • 163 просмотра
Решения вопроса 2
С краями ошиблись: 3 бита (3 вопроса) — это числа от 0 до 7.
Каждым вопросом уточняется бит, от старших к младшим:
0  000
1  001
2  010
3  011
4  100 - четыре?  - больше (старший бит 1xx )
5  101
6  110 - шесть? - больше ( 11x )
7  111 - семь – ага
Ответ написан
@Mercury13
Программист на «си с крестами» и не только
ceil(log2(n + 1))

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

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

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Bnovo Санкт-Петербург
от 110 000 до 140 000 ₽
Spice IT Recruitment Москва
от 160 000 до 200 000 ₽
СофтТелематика Москва
от 120 000 до 180 000 ₽
04 мар. 2021, в 22:39
2500 руб./за проект
04 мар. 2021, в 22:15
10000 руб./за проект