все Python 3Алгоритмы и структуры данныхпонятие

Бинарный поиск

поиск

Поиск в отсортированном массиве за O(log n). Каждый шаг делит область поиска пополам.

Синтаксис

def binary_search(arr, target):

Главная ловушка — данные обязаны быть отсортированы: на неотсортированном списке поиск не падает, а тихо возвращает неверный ответ. Ради одной проверки сортировать невыгодно: O(n log n) на сортировку дороже обычного оператора in за O(n), выигрыш появляется, когда по одному и тому же массиву ищут многократно. Писать его руками обычно незачем — bisect_left вернёт позицию вставки, останется сравнить элемент на этой позиции с искомым; переполнения (lo + hi), из-за которого этот алгоритм годами ломался в C и Java, в Python не бывает.

Примеры

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
print(binary_search([1,3,5,7,9,11], 7))  # → 3
print(binary_search([1,3,5,7,9,11], 6))  # → -1

# bisect — стандартная библиотека
import bisect
arr = [1,3,5,7,9]
print(bisect.bisect_left(arr, 5))  # → 2 (позиция для вставки)
print(bisect.bisect_right(arr, 5))  # → 3

# Рекурсивный вариант
def bs_rec(arr, target, lo=0, hi=None):
    if hi is None: hi = len(arr)-1
    if lo > hi: return -1
    mid = (lo+hi)//2
    if arr[mid] == target: return mid
    elif arr[mid] < target: return bs_rec(arr, target, mid+1, hi)
    else: return bs_rec(arr, target, lo, mid-1)
print(bs_rec([2,4,6,8,10], 6))  # → 2

# Поиск первого вхождения дубликата
def first_occurrence(arr, target):
    lo, hi, result = 0, len(arr)-1, -1
    while lo <= hi:
        mid = (lo+hi)//2
        if arr[mid] == target:
            result = mid; hi = mid-1
        elif arr[mid] < target: lo = mid+1
        else: hi = mid-1
    return result
print(first_occurrence([1,2,2,2,3], 2))  # → 1

# Бинарный поиск ответа
def min_pages(pages, students):
    lo, hi = max(pages), sum(pages)
    def can_split(limit):
        count, cur = 1, 0
        for p in pages:
            if cur + p > limit: count+=1; cur=0
            cur += p
        return count <= students
    while lo < hi:
        mid = (lo+hi)//2
        if can_split(mid): hi=mid
        else: lo=mid+1
    return lo
print(min_pages([10,20,30,40], 2))  # → 60

# bisect.insort — вставка в отсортированный список
import bisect
arr2 = [1,3,5,9]
bisect.insort(arr2, 6)
print(arr2)  # → [1,3,5,6,9]

См. также

Открыть в полном глоссарииdocs.python.orgСообщить о неточности