Бинарный поиск python через рекурсию

Бинарный поиск на Python

В повседневной жизни мы постоянно ищем информацию или пытаемся найти решение возникших проблем. Например, просматривая результаты поиска в Интернете, мы выбираем статьи и ресурсы, которые нам кажутся наиболее подходящими. Но поиск не всегда происходит одинаково, есть много подходов. Один из них — бинарный поиск.

Что такое алгоритм поиска?

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

Существуют различные типы поисковых алгоритмов.

Алгоритмы линейного поиска — самые простые из всех. Как следует из названия, они действуют последовательно.

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

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

Бинарный поиск

Алгоритмы бинарного поиска возвращают позицию искомого значения в отсортированном списке. В своей работе они используют подход «разделяй и властвуй».

Линейный и бинарный поиск — это примеры простых алгоритмов поиска.

При линейном поиске вы перебираете список, сравнивая каждое значение с искомым. При бинарном поиске сперва находится серединный элемент списка, который и сравнивается с искомым значением.

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

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

Алгоритмы сортировки

Алгоритмы сортировки принимают на вход несортированный список и возвращают список с элементами, расположенными в определенном порядке (чаще всего в порядке возрастания).

Алгоритмов сортировки, как и алгоритмов поиска, довольно много. Например, сортировка вставкой, быстрая сортировка, сортировка пузырьком и сортировка слиянием.

Как работает бинарный поиск

Алгоритм бинарного поиска использует технику, называемую «разделяй и властвуй». Эту же технику использует алгоритм сортировки слиянием.

В алгоритмах бинарного поиска метод «разделяй и властвуй» работает следующим образом:

• Алгоритм разбивает список на левую и правую части, разделенные серединным элементом.
• Для хранения искомого значения создается переменная.
• Алгоритм выбирает серединный элемент и сравнивает его с искомым значением.
• Если сравниваемые элементы равны, то процесс завершается.
• В противном случае серединный элемент либо больше, либо меньше искомого значения. Если он больше, дальнейший поиск происходит в левой части списка. Если серединный элемент меньше искомого, дальше поиск идет в правой части списка.

Этот метод можно реализовать с помощью рекурсии или итераций.

Примеры бинарного поиска в реальной жизни

Возможно, вы не осознаете этого, но мы постоянно используем бинарный поиск. Например, мы можем искать:

• слово в словаре
• книгу в определенном отделе в библиотеке
• элемент в отсортированном списке
• студентов ростом выше 5 футов 3 дюймов в ряду студентов, построенных по росту.

Пошаговый разбор бинарного поиска

Прежде всего, перед выполнением поиска необходимо отсортировать список.

Затем создается переменная, в которой хранится искомое значение.

Далее список делится на две части. Чтобы найти индекс серединного элемента в списке, суммируем первый и последний индексы.

Если вычисленное значение индекса серединного элемента является дробным числом (например, 3,45), то в качестве индекса мы берем целую часть.

Затем мы сравниваем искомое значение и серединный элемент.

Условие 1. Серединный элемент и есть искомое значение

Если серединный элемент равен искомому значению, возвращается позиция, на которой находится значение, и процесс завершается.

if middle element == to_search return position of middle element *code ends*

Используем в качестве примера изображение выше.

Серединный элемент = 23, искомое значение to_search = 23. Сравнивая эти два значения, мы видим, что они равны. В списке 23 появляется под индексом 2. Код возвращает 2, и процесс завершается.

Условие 2. Искомое значение больше или меньше серединного элемента

Если средний элемент не равен to_search , то мы проверяем следующие сценарии.

Сценарий 1. Серединный элемент больше, чем искомое значение

if middle element > to_search

• Поиск смещается в левую сторону, так как искомое значение меньше серединного элемента.
• Позиция серединного элемента сдвигается влево на 1 ( new_position = mid_index — 1 ).
• Начинается новый поиск — среди всех значений от начала списка до new_position .

Вернемся к нашему примеру.

middle element = 23 to_search = 4 if 23 > 4

Мы перемещаемся в левую часть, потому что там хранятся все числа меньше 23. Число 23 находится на позиции с индексом 2. Граница нового поиска на единицу меньше: new_position = index(23) — 1 = 2-1 = 1 . Новый поиск будет происходить среди элементов от начала списка до индекса 1.

Сравнивая новый серединный элемент (4) с искомым значением (4), мы видим, что они равны. Поэтому поиск прекращается. На выходе мы получаем позицию элемента с искомым значением — индекс 0.

Сценарий 2. Серединный элемент меньше искомого значения

• Поиск перемещается в правую сторону, так как искомое значение больше серединного элемента.
• Позиция серединного элемента сдвигается вправо на 1 ( new_position = index(middle element) + 1 ).
• Новый поиск начинается с new_position и заканчивается на последнем индексе списка.

Возвращаемся к нашему примеру.

middle element = 23 to_search = 32 if 23 > 32

Мы перемещаемся в правую часть, потому что там хранятся все числа больше 23. index(23) = 2, new_position = index(23) + 1 = 2+1 = 3. Новый поиск будет происходить среди элементов от индекса 3 до конца списка.

Сравнивая серединный элемент (32) с искомым значением (32), мы видим, что они равны. Поэтому поиск прекращается, и на выходе мы получаем индекс искомого значения — 4.

Методы, используемые в алгоритмах бинарного поиска

Есть два метода, с помощью которых можно реализовать технику «разделяй и властвуй» в поиске: итерационный и рекурсивный.

Итерационный метод реализации бинарного поиска

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

Код на Python для бинарного поиска, реализованного итерационным методом:

def binary_search(list_num , to_search): first_index = 0 size = len(list_num) last_index = size - 1 mid_index = (first_index + last_index) // 2 # print(mid_index) mid_element = list_num[mid_index] # print(mid_element) is_found = True while is_found: if first_index == last_index: if mid_element != to_search: is_found = False return " Does not appear in the list" elif mid_element == to_search: return f" occurs in position " elif mid_element > to_search: new_position = mid_index - 1 last_index = new_position mid_index = (first_index + last_index) // 2 mid_element = list_num[mid_index] if mid_element == to_search: return f" occurs in position " elif mid_element < to_search: new_position = mid_index + 1 first_index = new_position last_index = size - 1 mid_index = (first_index + last_index) // 2 mid_element = list_num[mid_index] if mid_element == to_search: return f"occurs in position " list_container = [16 , 18 , 20 , 50 , 60 , 81 , 84 , 89] print(binary_search(list_container , 81)) print(binary_search(list_container , 10))

Теперь давайте посмотрим, что здесь происходит.

• Сначала мы передаем список и искомое значение ( to_search ) в качестве аргументов в функцию.
• В функции мы создаем переменную first_index и присваиваем ей значение «0». Индексация списка всегда начинается с нуля.
• Затем мы создаем еще четыре переменных: size для хранения длины списка, last_index для хранения индекса последнего элемента, mid_index для хранения операции нахождения индекса серединного элемента и mid_element для хранения серединного элемента, получаемого из списка по индексу mid_index .
• После этого мы вводим цикл while . В нем мы создаем переменную с именем is_found и устанавливаем ее в значение True. Это условие проверяет, найден ли искомый элемент.
• В цикле while мы проверяем все условия. Первое условие — проверить, равны ли серединный элемент и значение переменной to_search . Если да, то возвращается позиция серединного элемента.
• Затем мы проверяем второе условие (если серединный элемент != искомый элемент), что приводит нас к двум сценариям:
  • Если серединный элемент больше искомого, то new_position сдвинется влево на единицу. Поиск начнется с начала списка и закончится на new_position , которая будет новым последним индексом списка.
  • Если серединный элемент меньше искомого, то new_position сдвигается на единицу вправо. Поиск начнется с new_position (нового первого индекса списка) и закончится на последнем индексе списка.

  Обработка ошибок

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

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

  Вывод результатов

  Последний шаг — вызов функции и вывод результата.

  Если элемент находится в списке, то выводится его позиция.

  

  Если элемента в списке нет, то на выходе получаем строку:

  

  Рекурсивный метод реализации бинарного поиска

  Функция считается рекурсивной, если для решения задачи она обращается к самой себе или к предыдущему(им) члену(ам). Рекурсивная функция является повторяющейся и выполняется последовательно. Она начинается со сложной задачи и разбивает ее на более простые формы.

  Реализация кода на Python для бинарного поиска с использованием рекурсии немного проще и короче:

  def binary_search(list_num, first_index, last_index, to_search): if last_index >= first_index: mid_index = (first_index + last_index) // 2 mid_element = list_num[mid_index] if mid_element == to_search: return f" occurs in position " elif mid_element > to_search: new_position = mid_index - 1 # new last index is the new position return binary_search(list_num, first_index, new_position, to_search) elif mid_element < to_search: new_position = mid_index + 1 # new first index is the new position return binary_search(list_num, new_position, last_index, to_search) else: return " Does not appear in the list" list_container = [ 1, 9, 11, 21, 34, 54, 67, 90 ] search = 34 first = 0 last= len(list_container) - 1 print(binary_search(list_container,first,last,search))

  • Сначала функция принимает четыре аргумента: первый и последний индекс, список и искомое значение.
  • Затем мы проверяем, больше или равно значение последнего индекса значению первого. Если условие истинно, мы присваиваем операцию поиска индекса серединного элемента переменной mid_index . В дальнейшем серединный элемент будет получен из списка при помощи индекса.
  • В блоке if мы проверяем, равны ли серединный элемент и переменная to_search . Если да, то будет возвращена позиция элемента.
  • Затем мы проверяем второе условие (серединный элемент не равен искомому), что приводит нас к двум сценариям:
    • Если серединный элемент больше, чем искомый, то new_position сдвинется на единицу влево. Новый поиск будет происходить среди элементов от начала списка и до new_position . Мы возвращаем функцию и передаем new_position в качестве последнего индекса.
    • Если серединный элемент меньше искомого, new_position сдвигается на единицу вправо. Новый поиск будет происходить среди элементов от new_position до конца списка. Мы возвращаем функцию и передаем new_position в качестве первого индекса.

    Если элемент находится в списке, то выводится его позиция:

    

    Если элемента в списке нет, выводится строка с сообщением:

    

    Заключение

    Теперь вы знаете, что такое бинарный поиск и как работают алгоритмы бинарного поиска. Мы рассмотрели реализацию такого алгоритма на Python, применив итерационный и рекурсивный подход.

    Источник