Binary Search

Binary Search

# O(log n) -- requires sorted array
def binary_search(arr, target) -> int:
    lo, hi = 0, len(arr)-1
    while lo <= hi:
        mid = lo + (hi-lo)//2  # avoid overflow
        if   arr[mid] == target: return mid
        elif arr[mid] <  target: lo = mid+1
        else:                    hi = mid-1
    return -1

# Lower bound -- first index >= target
def lower_bound(arr, target) -> int:
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo+hi)//2
        if arr[mid] < target: lo = mid+1
        else:                  hi = mid
    return lo

# Binary search on answer (classic technique)
# 'Can I do X with mid units?' -- find minimum mid that works
def min_days_to_make_bouquets(bloom, m, k):
    def feasible(days):
        flowers = bouquets = 0
        for b in bloom:
            if b <= days: flowers += 1
            else: flowers = 0
            if flowers == k: bouquets += 1; flowers = 0
        return bouquets >= m
    lo, hi = min(bloom), max(bloom)
    while lo < hi:
        mid = (lo+hi)//2
        if feasible(mid): hi = mid
        else: lo = mid+1
    return lo