all Python 3Algorithms & data structuresterm

Binary search

A search in a sorted array in O(log n). Every step halves the range being searched.

Syntax

def binary_search(arr, target):

The core trap is that the data must already be sorted: on an unsorted list the search does not raise anything, it just quietly returns a wrong answer. Sorting for the sake of one lookup does not pay off — O(n log n) costs more than a plain in check at O(n); the win appears when the same array is searched many times. You rarely need to hand-roll it: bisect_left gives the insertion point and you only compare the item sitting there with the target, and the (lo + hi) overflow that broke this algorithm for years in C and Java cannot happen in Python.

Examples

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]

Binary search

Syntax

Examples

See also