Содержание материала
Описание алгоритма
- Находится средний элемент последовательности. Для этого первый и последний индексы связываются с переменными, а индекс среднего элемента вычисляется.
- Значение среднего элемента сравнивается с искомым значение. В зависимости от того, больше оно или меньше значения среднего элемента, дальнейший поиск будет происходить только в левой или только в правой половинах массива. Если значение среднего элемента оказывается равным искомому, поиск завершается.
- Иначе одна из границ исследуемой последовательности сдвигается. Если искомое значение больше значения среднего элемента, то нижняя граница сдвигается за средний элемент на один элемент справа. Если искомое значение меньше значения среднего элемента, то верхняя граница сдвигается на элемент перед средним.
- Снова находится средний элемент теперь уже в выбранной половине. Описанный выше алгоритм повторяется для данного среза.
Видео
Линейный поиск
Линейный поиск — это один из самых простых и понятных алгоритмов поиска. Мы можем думать о нем как о расширенной версии нашей собственной реализации оператора in в Python.
Суть алгоритма заключается в том, чтобы перебрать массив и вернуть индекс первого вхождения элемента, когда он найден:
Итак, если мы используем функцию для вычисления:
То получим следующий результат:
Это индекс первого вхождения искомого элемента, учитывая, что нумерация элементов в Python начинается с нуля.
Временная сложность линейного поиска равна O(n). Это означает, что время, необходимое для выполнения, увеличивается с увеличением количества элементов в нашем входном списке lys.
Линейный поиск не часто используется на практике, потому что такая же эффективность может быть достигнута с помощью встроенных методов или существующих операторов. К тому же, он не такой быстрый и эффективный, как другие алгоритмы поиска.
Линейный поиск хорошо подходит для тех случаев, когда нам нужно найти первое вхождение элемента в несортированной коллекции. Это связано с тем, что он не требует сортировки коллекции перед поиском (в отличие от большинства других алгоритмов поиска).
Зачем использовать Python для поиска?
Python очень удобочитаемый и эффективный по сравнению с такими языками программирования, как Java, Fortran, C, C++ и т. д. Одним из ключевых преимуществ использования Python для реализации алгоритмов поиска является то, что вам не нужно беспокоиться о приведении или явной типизации.
В Python большинство алгоритмов поиска, которые мы обсуждали, будут работать так же хорошо, если мы ищем строку. Имейте в виду, что понадобится внести изменения в код для алгоритмов, которые используют искомый элемент для числовых вычислений, например алгоритм интерполяционного поиска.
Python также подходит, если вы хотите сравнить производительность различных алгоритмов поиска для вашего dataset’а. Создание прототипа на Python проще и быстрее, потому что вы можете сделать больше с меньшим количеством строк кода.
Чтобы сравнить производительность наших реализованных алгоритмов, в Python мы можем использовать библиотеку time:
Итерационный бинарный поиск в Python
Сначала мы реализуем двоичный поиск с итерационным методом. Мы будем повторять набор операторов и перебирать каждый элемент списка. Мы найдем среднее значение, пока поиск не завершится.
Разберемся в следующей программе итерационного метода.
Пример:
Выход:
Объяснение:
В приведенной выше программе:
- Мы создали функцию под названием binary_search(), которая принимает два аргумента – список для сортировки и число для поиска.
- Мы объявили две переменные для хранения наименьшего и наибольшего значений в списке. Начальное значение low присваивается 0, high – len (list1) – 1, а mid – 0.
- Затем мы объявили цикл while с условием, что наименьшее значение равно и меньше наибольшего. Цикл while будет повторяться, если число еще не найдено.
- В цикле while мы находим среднее значение и сравниваем значение индекса с искомым числом.
- Если значение среднего индекса меньше n, мы увеличиваем среднее значение на 1 и присваиваем ему значение. Поиск перемещается влево.
- В противном случае уменьшите среднее значение и назначьте его максимальному. Поиск переместится в правую сторону.
- Если n равно среднему значению, верните mid.
- Это будет происходить до тех пор, пока минимум не станет равным и меньше максимума.
- Если мы дойдем до конца функции, значит, элемента нет в списке. Возвращаем -1 вызывающей функции.
Рассмотрим рекурсивный метод двоичного поиска.
Реализация в модуле bisect
bisect.insort(list, elem, lo=0, hi=len(a)), или bisect.insort_right(list, elem, lo=0, hi=len(a)) — вставка элемента в отсортированный список, при этом elem располагается как можно правее (все элементы, равные ему, остаются слева). Параметры lo и hi (здесь и в других функциях) могут быть использованы для указания подмножества списка, которое нужно учитывать; по умолчанию используется весь список.
bisect.insort_left(list, elem, lo=0, hi=len(a)) — вставка элемента в отсортированный список, при этом elem располагается как можно левее (все элементы, равные ему, остаются справа).
bisect.bisect(list, elem, lo=0, hi=len(a)), или bisect.bisect_right(list, elem, lo=0, hi=len(a)) — поиск места для вставки элемента в отсортированный список, таким образом, чтобы elem располагался как можно правее.
bisect.bisect_left(list, elem, lo=0, hi=len(a)) — поиск места для вставки элемента в отсортированный список, таким образом, чтобы elem располагался как можно левее.
Двоичный поиск в разбивке по сложности Python
Какова сложность двоичного поиска? Это хороший вопрос.
Алгоритм двоичного поиска имеет сложность в лучшем случае O (1). Это происходит, когда первое сравнение соответствует элементу, который вы ищете.
Средняя и наихудшая сложность для двоичного поиска составляет O (log n). Это означает, что время, необходимое для выполнения поиска, увеличивается логарифмически в зависимости от того, сколько элементов требуется для поиска в списке.