Какое максимальное количество операций в бинарном поиске?
С краями ошиблись: 3 бита (3 вопроса) — это числа от 0 до 7. 
Каждым вопросом уточняется бит, от старших к младшим:0  000
1  001
2  010
3  011
4  100 - четыре?  - больше (старший бит 1xx )
5  101
6  110 - шесть? - больше ( 11x )
7  111 - семь – ага
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, что, по предположению индукции, невозможно.