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

Метод 1: итеративный двоичный поиск
Метод итеративного двоичного поиска включает в себя установку нижнего и верхнего указателей для обозначения диапазона пространства поиска. Затем вычисляется средняя точка, и если целевое значение равно значению в средней точке, поиск завершается успешно. Если целевое значение меньше, верхний указатель обновляется до средней точки – 1. И наоборот, если целевое значение больше, нижний указатель обновляется до средней точки + 1. Этот процесс продолжается до тех пор, пока целевое значение не будет найдено или не начнется поиск. место исчерпано.

def iterative_binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # Target value not found

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

def recursive_binary_search(arr, target, low, high):
    if low > high:
        return -1  # Target value not found
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return recursive_binary_search(arr, target, mid + 1, high)
    else:
        return recursive_binary_search(arr, target, low, mid - 1)

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

def leftmost_occurrence_binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    result = -1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            result = mid
            high = mid - 1  # Continue searching towards the left
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return result
def rightmost_occurrence_binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    result = -1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            result = mid
            low = mid + 1  # Continue searching towards the right
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return result

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