7.2. Сокращение области поиска

Определения и обозначения

Область поиска — часть упорядоченного набора, в которой ещё может находиться искомый элемент. Сначала такой областью служит весь набор, а потом она становится всё меньше. Это понятие помогает точно понимать, какие элементы осталось проверять.

Упорядоченный набор — последовательность элементов, расположенных по возрастанию или по убыванию. Например, числа 2, 5, 8, 11 идут по возрастанию, а 11, 8, 5, 2 — по убыванию. Порядок нужен, чтобы по сравнению значений решать, какую часть набора можно исключить.

Двоичный поиск — способ находить элемент в упорядоченном наборе, каждый раз сокращая область поиска примерно вдвое. Вместо проверки всех элементов по очереди мы сравниваем искомое значение со средним. Такой способ нужен, чтобы быстрее находить значения и определять их отсутствие.

Как это устроено

Двоичный поиск требует упорядоченных данных, потому что сравнение со средним элементом должно сообщать, где искать дальше. Например, в наборе по возрастанию все элементы слева от среднего меньше него, а все справа — больше. Если набор перемешан, такого правила нет, и исключённая половина может содержать ответ.

В начале область поиска охватывает весь набор: пока ни один элемент не исключён. Для проверки выбирают средний элемент этой области. Он делит возможные места на левую и правую части, поэтому одно сравнение помогает решить, какую часть оставить.

Затем сравнивают средний элемент с искомым. Если набор упорядочен по возрастанию и искомое меньше среднего, справа искать незачем: там значения ещё больше. Если искомое больше среднего, исключают левую часть по той же причине и продолжают справа.

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

Если среднее значение совпало с искомым, элемент найден и поиск завершается. Если же область опустела, значит, все возможные места исключены и искомого элемента в наборе нет. Таким образом, у алгоритма есть два результата: найденное значение или вывод об отсутствии элемента.

Шаги двоичного поиска

Пользуйся таблицей после каждого сравнения: сначала определи, меньше, больше или равен искомый элемент среднему. Затем измени границы области согласно нужной строке, исключив уже проверенную середину. Для набора по убыванию направления «лево» и «право» меняются местами.

Разбор задач

Задача 1. Найти число 11 в списке 2, 5, 8, 11, 14

Список упорядочен по возрастанию, поэтому можно применить двоичный поиск. Будем каждый раз сравнивать искомое число с серединой текущей области. Проверенный элемент не включаем в следующую область.

1. В середине всего списка стоит 8. Число 11 больше 8, поэтому оставляем правую часть: 11, 14.
2. Середина оставшейся области — 11. Сравниваем его с искомым числом.
3. Значения равны, значит, поиск завершён.

Ответ: число 11 найдено. Проверены элементы 8 и 11, всего выполнено два сравнения. Мы не проверяли 2, 5 и 14, потому что порядок списка позволил исключить их.

Задача 2. Проверить, есть ли число 10 в списке 3, 6, 9, 12, 15, 18, 21

Список также упорядочен по возрастанию, поэтому после каждого сравнения можно отбросить половину. Нужно не просто искать совпадение, но и следить, не исчезла ли область поиска. Если она опустеет, числа 10 в списке нет.

1. Средний элемент всего списка — 12. Число 10 меньше, поэтому оставляем левую часть: 3, 6, 9.
2. Средний элемент оставшейся части — 6. Число 10 больше, поэтому оставляем правую часть: 9.
3. Сравниваем 10 с 9. Искомое больше, поэтому после исключения проверенного элемента область становится пустой.

Ответ: числа 10 в списке нет. Были проверены 12, 6 и 9, после чего не осталось возможных элементов. Пустая область — основание сделать вывод об отсутствии числа.

Задача 3. Найти 27 в упорядоченном списке из 16 элементов и оценить число сравнений

Значения шестнадцати элементов не указаны, поэтому проследить конкретные проверки нельзя. Но можно описать сокращение области, если 27 присутствует и на каждом шаге сравнение оставляет подходящую половину. Для оценки берём наибольшее число сравнений, нужное для нахождения элемента.

1. Сначала в области 16 элементов; после первого сравнения остаётся примерно 8.
2. После второго сравнения остаётся примерно 4 элемента, после третьего — примерно 2.
3. Ещё одно сравнение позволяет проверить оставшийся возможный элемент: число сравнений не превысит 4.

Ответ: для списка из 16 элементов потребуется не более 4 сравнений, если 27 в нём есть. Точный путь зависит от значений элементов и положения 27. Если число отсутствует, поиск продолжается до опустевшей области.

Типичные ошибки

Искать в неупорядоченном наборе. Так поступают, потому что кажется, будто середина списка всегда делит элементы на меньшие и большие. Но это верно только при соблюдении порядка. Перед поиском проверь, расположены ли данные по возрастанию или убыванию.

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

Не исключать уже проверенный средний элемент. Если оставить его в области, алгоритм может повторно выбирать то же значение и зациклиться. После неравного сравнения сдвигай границу за середину. Убедись, что новая область стала меньше предыдущей.

Считать, что элемент обязательно найден. Так можно ошибиться, когда после нескольких шагов область опустела. Если проверять больше нечего, совпадения нет. Следи за границами и завершай поиск сообщением об отсутствии элемента.

Связь с другими темами

Для двоичного поиска нужно уметь сравнивать числа или другие элементы и понимать порядок возрастания и убывания. Он связан с линейным поиском: сравни оба способа на одном наборе и посчитай проверки. Двоичный поиск особенно пригодится для отсортированных списков, каталогов и таблиц данных. В каждом случае его преимущество сохраняется только при наличии порядка.

Что запомнить

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