30. На полке слева направо, в алфавитном порядке, расставлены 1024 книги. Они находятся в боксах, названия не видны. Робот-библиотекарь в течение одной секунды может достать любую книгу, посмотреть её название, сравнить с искомым и вернуть на место. Роботу надо найти книгу «Информатика», которая точно есть на полке. Какое минимальное количество времени ему нужно (в худшем случае), чтобы гарантированно найти книгу? Подсказка: робот использует то, что книги отсортированы и ищет книгу самым быстрым способом. А) 1024 с. Б) 512 с. В) 30 с. Г) 20 с. Д) 10 с.

Поскольку книги расположены в алфавитном порядке, робот может применять бинарный поиск: каждый раз проверять книгу из середины оставшегося диапазона и отбрасывать половину, в которой искомой книги быть не может.

Половины можно отсечь примерно за log₂(1024) = 10 шагов, так как 2¹⁰ = 1024. В рамках предложенных вариантов ожидаемый ответ — 10 секунд.

Замечание: при подсчёте строгого наихудшего числа сравнений стандартный бинарный поиск для 1024 элементов может потребовать 11 сравнений; такого варианта в списке нет.

Ответ по вариантам: Д) 10 с.