Последовательный просмотр и деление диапазона
Линейный поиск проверяет элементы по очереди. Он подходит для неупорядоченного списка и не требует подготовки. В худшем случае придется просмотреть весь список, поэтому число проверок растет пропорционально его длине. Двоичный поиск работает иначе: сравнивает цель со средним элементом и оставляет только подходящую половину диапазона. Для него нужен отсортированный набор и согласованное правило сравнения. В массиве с быстрым доступом по индексу число сравнений растет логарифмически. Ошибка возникает, если список упорядочили по одному полю, а ищут по другому. Отдельно нужно решить, какой результат вернуть при нескольких одинаковых значениях: любое совпадение, первое или последнее.
Что скрывается за словом сортировка
Сортировка переставляет элементы согласно ключу: числу, дате, строке или сочетанию признаков. Например, заказы можно расположить по дате, а внутри одной даты по номеру. Сортировка вставками постепенно строит упорядоченную часть, помещая очередной элемент на нужное место. На почти упорядоченных данных она может выполнять мало перемещений, но в худшем случае требует квадратичного числа операций. Сортировка слиянием делит набор на части, сортирует их и объединяет; ее типичная оценка времени составляет n log n, а распространенная реализация для массивов использует дополнительную память. Эти оценки описывают рост затрат, а не точное количество секунд на любом устройстве.
Проверяйте свойства, а не только красивый пример
Устойчивой называют сортировку, сохраняющую исходный порядок элементов с равными ключами. Это важно, когда предыдущая группировка несет смысл. Другой вопрос касается памяти: меняется ли исходный массив или создается новый. В практической задаче учитывают также стоимость сравнения, размер записи и частоту обновлений. Для одного запроса по короткому списку простой просмотр часто удобнее отдельной сортировки. Для множества запросов по неизменному массиву подготовка может окупиться. Проверки должны включать пустой список, один элемент, повторяющиеся значения, уже упорядоченный набор и обратный порядок. Если найден неверный ответ, ускорять алгоритм пока рано: сначала исправляют определение границ и условий завершения.
Попробуйте на практике
Сравните два способа поиска вручную и проверьте их на граничных случаях.
- Запишите восемь различных чисел в произвольном порядке. Найдите выбранное число последовательным просмотром и посчитайте сравнения.
- Отсортируйте те же числа по возрастанию. Выполните двоичный поиск, каждый раз записывая левую границу, правую границу и середину оставшегося диапазона.
- Повторите поиск для числа меньше минимального и для отсутствующего числа между двумя соседними значениями. Зафиксируйте момент завершения.
- Добавьте повторяющееся значение и сформулируйте, нужен ли любой подходящий индекс или первый. Объясните, почему эта формулировка может изменить алгоритм.
Как проверить результат. Для каждого запроса указан правильный результат, диапазон двоичного поиска строго сокращается, а стоимость предварительной сортировки не скрыта в сравнении способов.
Частые вопросы
Почему двоичный поиск нельзя применять к произвольному списку?
Сравнение со средним элементом должно позволять исключить половину данных. Без упорядоченности нужное значение может находиться в любой половине, поэтому такое исключение необоснованно.
Достаточно ли выбрать алгоритм с лучшей асимптотикой?
Нет. Для небольшого объема важны простота и постоянные затраты, для большого еще память и структура данных. Асимптотика помогает сравнивать рост работы, но не заменяет измерение на характерных примерах.
Самостоятельный разбор темы. Содержание конкретной обучающей программы здесь не представлено.