Какой алгоритм гарантированно найдёт в отсортированном списке нужное число быстрее полного перебора при большом количестве элементов? Выбери ответ.

Краткий ответ: бинарный поиск.

Почему именно он

В условии есть ключевое слово — отсортированный список. Именно на нём держится бинарный поиск:

1. Смотрим на элемент в середине списка.
2. Сравниваем с искомым числом.
3. Если совпало — готово.
4. Если искомое меньше середины — правая половина нам уже не нужна, ищем только в левой. Если больше — наоборот.
5. Повторяем с новой половиной, пока не останется один элемент.

Каждый шаг отбрасывает половину оставшихся данных, поэтому число шагов растёт как \(\log_2 n\), а у полного перебора — как \(n\):

\[ \text{бинарный поиск: } \log_2 n \qquad \text{линейный поиск: } n \]

Почему остальные варианты не подходят

• Случайный выбор элемента — не гарантирует, что нужное число вообще попадётся: можно тыкать наугад и не найти.
• Линейный поиск — это и есть полный перебор, он медленнее.
• Перемешивание списка — это вообще не поиск, к тому же оно разрушает сортировку, без которой бинарный поиск работать не может.

Проверка на маленьком примере

Список: \(1, 3, 5, 7, 9, 11, 13, 15\). Ищем \(11\).

• Середина — \(7\). Так как \(11 > 7\), берём правую часть: \(9, 11, 13, 15\).
• Середина — \(11\). Нашли! Всего 2 сравнения.
• Перебором пришлось бы проверить \(1, 3, 5, 7, 9, 11\) — шесть сравнений.

Главный вывод: бинарный поиск выигрывает за счёт того, что отсортированный список позволяет за одно сравнение «выбросить» половину вариантов. Чем больше элементов, тем заметнее выигрыш.