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

Метод 1: рекурсивный двоичный поиск
Один из самых популярных способов реализации двоичного поиска — рекурсия. Вот пример функции рекурсивного двоичного поиска:

def binary_search_recursive(lst, target, l, r):
    if r >= l:
        mid = l + (r - l) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] > target:
            return binary_search_recursive(lst, target, l, mid - 1)
        else:
            return binary_search_recursive(lst, target, mid + 1, r)
    else:
        return -1

Метод 2: итеративный двоичный поиск
Другой способ реализации двоичного поиска — итеративный цикл. Этот подход позволяет избежать накладных расходов на рекурсию и часто оказывается более эффективным. Вот пример итеративной функции двоичного поиска:

def binary_search_iterative(lst, target):
    l, r = 0, len(lst) - 1
    while l <= r:
        mid = l + (r - l) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            l = mid + 1
        else:
            r = mid - 1
    return -1

Метод 3: двоичный поиск с ранним выходом
В некоторых сценариях может потребоваться досрочное прекращение двоичного поиска, если выполняется определенное условие. Например, если список отсортирован по возрастанию и вы ищете первое вхождение целевого элемента, вы можете изменить функцию двоичного поиска следующим образом:

def binary_search_early_exit(lst, target):
    l, r = 0, len(lst) - 1
    while l <= r:
        mid = l + (r - l) // 2
        if lst[mid] == target:
            if mid == 0 or lst[mid - 1] != target:
                return mid
            else:
                r = mid - 1
        elif lst[mid] < target:
            l = mid + 1
        else:
            r = mid - 1
    return -1

Метод 4: двоичный поиск с использованием пользовательских компараторов
Двоичный поиск также можно использовать с пользовательскими компараторами при работе с более сложными структурами данных. Например, если у вас есть список объектов и вы хотите выполнить поиск целевого объекта, используя определенное значение атрибута, вы можете определить собственную функцию сравнения и соответствующим образом изменить двоичный поиск.

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