Шаблоны двоичного поиска в Python

Что такое двоичный поиск?

Двоичный поиск — это алгоритм поиска, который каждый раз делит интервал поиска пополам. Это также означает, что временная сложность двоичного поиска равна O(log n).

Шаблоны

Двоичный поиск может:

• найти один элемент в отсортированном массиве
• найти первый индекс, удовлетворяющий условию

Найти одиночный элемент в отсортированном массиве

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

Найти первый индекс, удовлетворяющий условию

Нахождение первого индекса, удовлетворяющего условию, аналогично нахождению первого истинного значения в массиве true-false.
например: [False, ... False, True, ... True].

Следует отметить следующее:

• left и right должны включать и read & write space
• цикл while останавливается, когда left == right
• после завершения цикла while:

def condition():
    pass

def binary_search(arr):
    left, right = 1, len(arr)-1
    while left < right:
        mid = (left + right) // 2
        if condition():
            right = mid
        else:
            left = mid + 1
    return left