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

Метод 1: два двоичных поиска.
Один простой подход — выполнить два отдельных двоичных поиска: один для поиска первого вхождения, другой для поиска последнего вхождения.

def find_first_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            result = mid
            right = mid - 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result
def find_last_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            result = mid
            left = mid + 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result
def find_first_and_last_occurrence(arr, target):
    first = find_first_occurrence(arr, target)
    last = find_last_occurrence(arr, target)
    return first, last

Метод 2: модифицированный двоичный поиск
Альтернативный подход включает изменение алгоритма двоичного поиска для совместного поиска первого и последнего вхождений.

def find_first_and_last_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    first, last = -1, -1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            first = mid
            right = mid - 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            last = mid
            left = mid + 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return first, last

Метод 3: рекурсивный двоичный поиск
Мы также можем реализовать рекурсивную версию алгоритма двоичного поиска для поиска первого и последнего вхождений.

def find_first_and_last_occurrence(arr, target):
    first = find_first_occurrence(arr, target, 0, len(arr) - 1)
    last = find_last_occurrence(arr, target, 0, len(arr) - 1)
    return first, last
def find_first_occurrence(arr, target, left, right):
    if left > right:
        return -1
    mid = left + (right - left) // 2
    if arr[mid] == target and (mid == 0 or arr[mid - 1] != target):
        return mid
    elif arr[mid] < target:
        return find_first_occurrence(arr, target, mid + 1, right)
    else:
        return find_first_occurrence(arr, target, left, mid - 1)
def find_last_occurrence(arr, target, left, right):
    if left > right:
        return -1
    mid = left + (right - left) // 2
    if arr[mid] == target and (mid == len(arr) - 1 or arr[mid + 1] != target):
        return mid
    elif arr[mid] <= target:
        return find_last_occurrence(arr, target, mid + 1, right)
    else:
        return find_last_occurrence(arr, target, left, mid - 1)

В этой статье мы рассмотрели различные методы использования двоичного поиска для поиска первого и последнего вхождения числа в отсортированном массиве. Эти подходы обеспечивают эффективные решения этой проблемы, позволяя нам получить нужную информацию с временной сложностью O(log n), где n — размер массива. Освоив эти методы, вы сможете улучшить свое понимание алгоритмов двоичного поиска и применять их для решения различных задач программирования.