Закодим алгоритм бинарного поиска на Python!

Алгоритм бинарного поиска позволяет отыскать элемент в упорядоченном списке. Этот алгоритм довольно широко применяется для решения задач, в которых требуется отыскать индекс заданного элемента последовательности или выяснить, присутствует ли в этой последовательности искомый элемент. Конечно, в Python есть замечательный оператор in, который выдаст True или False при попытке отыскать с его помощью элемент в списке. Но этот вариант, так же как и линейный поиск, уступает по производительности бинарному поиску, так как справляется с поставленной задачей за O(N) шагов. В то время, как производительность бинарного поиска O(logN) шагов — за это его и любят 😉

Производительность бинарного поиска O(logN) шагов

Полезная информация

Кроме того, алгоритм бинарного поиска довольно прост в реализации и интуитивно понятен. В чем вы сейчас и убедитесь. Я кратко набросаю основные тезисы, а после — добавлю 2 варианта реализованного алгоритма. Если что-то будет не понятно из тезисов, код вам в помощь, друзья! 😉

Алгоритм бинарного поиска:

Цель: получить позицию искомого элемента в упорядоченном списке

Последовательсть действий при реализации алгоритма:

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

Производительность: Если данные содержат N элементов, то для итерации потребуется максимум O(logN) шагов.

Реализация: Бинарный поиск можно реализовать как рекурсивным, так и итеративным способом. Для большей наглядности сначала рассмотрим реализацию алгоритма итеративным способом на основе цикла while.

Реализуем бинарный поиск на Python итеративным способом:

def binary_search(lst, item):
    
	# определяем начальный и 
	#конечный элементы:
	first = 0
    last = len(lst) - 1    

    while first <= last:
		# находим средний элемент
        mid = (first + last) // 2

        if lst[mid] == item:
            return mid

		# если средний эл-т больше искомого:
        elif lst[mid] > item:
            last = mid — 1

		# если средний эл-т меньше искомого:
        else:
            first = mid + 1

    return None


# Протестируем на примере:
nums = [1, 3, 5, 7, 9, 11]
print(binary_search(nums, 7))

Бинарный поиск рекурсивным способом

В основе рекурсивного способа лежит вызов функцией самой себя:

def binary_search(lst, item, first, last):

    if first <= last:
        # находим средний элемент
        mid = (first + last) // 2

    if lst[mid] == item:
        return mid

    # если средний эл-т больше искомого:
    elif lst[mid] > item:
        return binary_search1(lst, item, first, mid-1)

    # если средний эл-т меньше искомого:
    elif lst[mid] < item:
        return binary_search1(lst, item, mid+1, last)

    else: 
        return None


# Протестируем на примере:
nums = [1, 3, 5, 7, 9, 11]
print(binary_search(nums, 7))

Вывод на экран: 3

У нас появился Telegram-канал для изучающих Python! Присоединяйтесь: вместе «питонить» веселее! 😉 Ссылка на канал: «Кодим на Python!»

Добавить комментарий