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

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1               # ищем в отрезке [lo, hi] включительно
    while lo <= hi:
        mid = (lo + hi) // 2
        print(f"  lo={lo}, hi={hi}, mid={mid}, nums[mid]={nums[mid]}")
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1                    # target правее
        else:
            hi = mid - 1                    # target левее
    return -1

nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(nums, 23))
print(binary_search(nums, 7))

def first_true(lo, hi, cond):
    """Первое x в [lo, hi), для которого cond(x) истинно (cond монотонно: F F F T T T)."""
    while lo < hi:
        mid = (lo + hi) // 2
        if cond(mid):
            hi = mid          # mid подходит — ответ mid или левее
        else:
            lo = mid + 1      # mid не подходит — ответ правее
    return lo

nums = [1, 2, 2, 2, 5, 7]
first = first_true(0, len(nums), lambda i: nums[i] >= 2)      # первое вхождение 2
after = first_true(0, len(nums), lambda i: nums[i] > 2)       # первое больше 2
print(first, after, "→ двойка встречается", after - first, "раза")

import bisect

scores = [10, 20, 20, 20, 30, 40]
print(bisect.bisect_left(scores, 20))       # первая позиция, куда можно вставить 20 — слева от равных
print(bisect.bisect_right(scores, 20))      # справа от равных
print(bisect.bisect_left(scores, 25))

bisect.insort(scores, 25)                   # вставка с сохранением порядка (поиск O(log n), вставка O(n))
print(scores)

def grade(score, breakpoints=(60, 70, 80, 90), grades="FDCBA"):
    return grades[bisect.bisect(breakpoints, score)]
print([grade(s) for s in (33, 60, 77, 89, 90, 100)])

events = [(1, "старт"), (5, "обед"), (9, "отчёт")]      # поиск по ключу (Python 3.10+)
i = bisect.bisect_right(events, 6, key=lambda e: e[0])
print("последнее событие до 6:", events[i - 1])

def min_capacity(weights, days):
    """Минимальная грузоподъёмность корабля, чтобы перевезти посылки по порядку за days дней."""
    def can_ship(capacity):
        need_days, load = 1, 0
        for w in weights:
            if load + w > capacity:
                need_days += 1
                load = 0
            load += w
        return need_days <= days

    lo, hi = max(weights), sum(weights)      # ответ точно в этом диапазоне
    while lo < hi:
        mid = (lo + hi) // 2
        if can_ship(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

print(min_capacity([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))

def isqrt(n):
    """Целая часть квадратного корня без math."""
    lo, hi = 0, n + 1
    while lo < hi:                       # первое x, у которого x*x > n
        mid = (lo + hi) // 2
        if mid * mid > n:
            hi = mid
        else:
            lo = mid + 1
    return lo - 1

print(isqrt(17), isqrt(10**20), isqrt(0))

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:                  # левая половина отсортирована
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                       # правая половина отсортирована
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0), search_rotated([4, 5, 6, 7, 0, 1, 2], 3))

def find_peak(nums):
    """Индекс любого элемента, который больше соседей."""
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1                            # подъём — пик правее
        else:
            hi = mid                                # спуск — пик здесь или левее
    return lo

print(find_peak([1, 2, 1, 3, 5, 6, 4]))