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