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