Конкурс "Бобер-2020"

Плотник в Бобровой Деревне использует 31 склад, пронумерованный от 1 до 31. Однажды, он забыл, сколько складов уже заполнил, но помнит, что заполнял их в порядке возрастания номеров.

Чтобы уменьшить количество открывания дверей, он действует следующим образом: Сначала, открывает склад со средним номером — склад №16. Затем: - если склад №16 пуст, он решает искать первый незаполненный склад в промежутке от №1 до №15, открывает опять средний склад — склад №8 — и повторяет процедуру; - если склад №16 заполнен, то нужный склад он ищет между №17 и №31, открывает средний склад — склад №24 — и повторяет процедуру. Вопрос После всех действий плотник обнаружил, что заполнены были склады от №1 до №15 включительно. Сколько дверей ему пришлось открыть? Решение: Двоичный поиск эффективно определяет положение искомого элемента (или его отсутствие) в упорядоченном наборе. Это один из базовых и важных алгоритмов. Если склады от №1 до №15 заполнены, то: - когда плотник открывает склад №16, он оказывается пуст (1-ая открытая дверь); - тогда плотник решает искать между №1 и №15, открывает склад №8, он оказывается заполнен (2-ая открытая дверь); - теперь он ищет между №9 и №15, открывает склад №12 — он заполнен (3-ья открытая дверь); - далее он ищет между №13 и №15, открывает склад №14 - он заполнен (4-ая открытая дверь); - наконец он открывает последний склад № 15 (5-ая дверь). Правильный ответ: 5