В задачах, когда нужно искать элемент в последовательности чисел (например в списке или массиве), проще всего использовать линейный поиск. То есть последовательно перебрать все элементы сравнивая их с искомым значением.
Такой алгоритм достаточно прост в написании и понимании, но на практике при работе с большими наборами данных оказывается достаточно затратен с точки зрения времени выполнения.
Для сокращения времени работы программы можно использовать вместо линейного поиска алгоритм бинарного поиска.
Бинарный поиск — тип поискового алгоритма, который последовательно делит пополам заранее отсортированный массив данных, чтобы обнаружить нужный элемент. Другие его названия — двоичный поиск, метод половинного деления, дихотомия.
Принцип работы алгоритма бинарного поиска
Основная последовательность действий алгоритма выглядит так:
- Сортируем массив данных.
- Делим его пополам и находим середину.
- Сравниваем срединный элемент с заданным искомым элементом.
- Если искомое число больше среднего — продолжаем поиск в правой части массива (если он отсортирован по возрастанию): делим ее пополам, повторяя пункт 3. Если же заданное число меньше — алгоритм продолжит поиск в левой части массива, снова возвращаясь к пункту 3.
В каких случаях используют бинарный поиск
Двоичный поиск подходит для нахождения позиций элемента в упорядоченном списке: в этом случае он эффективнее линейного, поскольку массив данных на каждом шаге разделяется надвое и одна половина сразу отбрасывается. Последовательная сложность двоичного метода в худшем и среднем случаях равна O(log n), в лучшем — O(1) (если обнаруживаем искомый элемент на первой итерации). Для сравнения: вычислительная сложность линейного поиска равна O(n) (обычный проход по всем элементам в поисках нужного).
У бинарного поиска есть недостаток — он требует упорядочивания данных по возрастанию. Сложность сортировки — не менее O(n log n). Поэтому, если список короткий, используется все-таки линейный поиск.
Применение бинарного поиска при решении задания 26 в ЕГЭ по информатике
Задача
В текстовом файле записан набор натуральных чисел, не превышающих 10 в 9 степени. Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар чётных чисел, что их среднее арифметическое тоже присутствует в файле, и чему равно наибольшее из средних арифметических таких пар.
Входные данные Первая строка входного файла содержит целое число 𝑁 – общее количество чисел в наборе. Каждая из следующих 𝑁 строк содержит одно число.
Решение на python с применением бинарного поиска
