Бинарный поиск на 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. Серединный элемент меньше искомого значения

if middle element < to_search

  • Поиск перемещается в правую сторону, так как искомое значение больше серединного элемента.
  • Позиция серединного элемента сдвигается вправо на 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"{mid_element} occurs in position {mid_index}"

        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"{mid_element} occurs in position {mid_index}"

        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"{mid_element} occurs in position {mid_index}"



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"{mid_element} occurs in position {mid_index}"
 
        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 в качестве первого индекса.
  • Последнее условие будет находиться на том же уровне, что и первый оператор if. Если параметр to_search не находится в списке, то будет возвращена строка.
  • Последний шаг — вызов функции и вывод результата на экран.

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

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

Заключение

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

Перевод статьи «Binary Search in Python – How to Code the Algorithm with Examples».

[customscript]techrocks_custom_after_post_html[/customscript]

[customscript]techrocks_custom_script[/customscript]

Похожие записи

Оставьте комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Прокрутить вверх