Binary Search — ২০ লাইনের কোড, ৯৯% মানুষ ভুল লেখে

from bisect import bisect_left, bisect_right


def lower_bound(a, x):
    """প্রথম i যেখানে a[i] >= x; না থাকলে len(a).
       INVARIANT: a[:lo]-র সব < x  এবং  a[hi:]-র সব >= x."""
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2        # lo ≤ mid < hi — progress guaranteed
        if a[mid] < x:
            lo = mid + 1                 # a[:lo]-র "< x" claim বজায়
        else:
            hi = mid                     # a[hi:]-র "≥ x" claim বজায়
    return lo                            # lo==hi: মিলনবিন্দুই উত্তর


def upper_bound(a, x):
    """প্রথম i যেখানে a[i] > x; INVARIANT: a[:lo] ≤ x < a[hi:]"""
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] <= x:                  # lower_bound থেকে একমাত্র পার্থক্য
            lo = mid + 1
        else:
            hi = mid
    return lo


def rotated_search(nums, target):
    """Rotated sorted array (distinct values) — O(log n).
       প্রতি ধাপে অন্তত একটা half sorted; target সেখানে range-fit করে কি না দেখে সিদ্ধান্ত।"""
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:                 # বাম half sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1                      # target সোজা half-এ
            else:
                lo = mid + 1
        else:                                     # ডান half sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1


def isqrt(n):
    """floor(sqrt(n)) — binary search ON THE ANSWER.
       Predicate P(m) = (m*m <= n) monotone decreasing; শেষ TRUE খোঁজা।"""
    if n < 2:
        return n
    lo, hi = 1, n // 2 + 1               # উত্তর এর ভেতরে থাকার গ্যারান্টি
    while lo < hi:
        mid = (lo + hi + 1) // 2         # UPPER mid — lo==mid infinite-loop আটকাতে
        if mid * mid <= n:
            lo = mid                     # P(mid) true → উত্তর ≥ mid
        else:
            hi = mid - 1                 # P(mid) false → উত্তর < mid
    return lo


# ================= exhaustive boundary tests =================

def run_tests():
    import math

    # --- n ∈ {0, 1, 2}: সব possible arrays, সব query positions ---
    tiny_cases = [
        [],
        [-7],
        [-7, 3],
        [3, -7][::1],          # unsorted guard — আমাদের contract sorted চায়
    ]
    tiny_sorted = [[], [5], [3, 9]]
    for a in tiny_sorted:
        for x in range(-10, 15):
            lb, ub = lower_bound(a, x), upper_bound(a, x)
            assert lb == bisect_left(a, x), (a, x, lb)
            assert ub == bisect_right(a, x), (a, x, ub)
            if lb < ub:                          # x আছে
                assert a[lb] == x and lb < ub
    assert lower_bound([], 1) == 0 and upper_bound([], 1) == 0

    # --- random cross-validation vs stdlib oracle ---
    import random
    rng = random.Random(777)
    for _ in range(20_000):
        n = rng.randint(0, 40)
        a = sorted(rng.randint(-50, 50) for _ in range(n))
        x = rng.randint(-55, 55)
        assert lower_bound(a, x) == bisect_left(a, x)
        assert upper_bound(a, x) == bisect_right(a, x)

    # --- rotated: brute-force oracle ---
    for _ in range(5_000):
        n = rng.randint(0, 30)
        base = sorted(rng.sample(range(-999, 999), n))
        target = rng.choice(base) if n and rng.random() < 0.7 else rng.randint(-999, 999)
        rot = rng.randrange(n) if n else 0
        rotated = base[rot:] + base[:rot] if n else []
        got = rotated_search(rotated, target)
        if got == -1:
            assert target not in rotated
        else:
            assert rotated[got] == target

    # --- isqrt: exhaustive 0..2000 + big values ---
    for n in range(0, 2001):
        assert isqrt(n) == math.isqrt(n), n
    for n in (10**12, 10**15 + 12345, 2**62, 2**63 - 1):
        assert isqrt(n) == math.isqrt(n), n

    print('lower_bound / upper_bound : 20k random + tiny-edge ALL PASS')
    print('rotated_search            : 5k brute-force validated PASS')
    print('isqrt                     : exhaustive 0..2000 + bigint PASS')


if __name__ == '__main__':
    run_tests()

প্রত্যাশিত output:

lower_bound / upper_bound : 20k random + tiny-edge ALL PASS
rotated_search            : 5k brute-force validated PASS
isqrt                     : exhaustive 0..2000 + bigint PASS

নিজে বাড়ান:

১. find_last(a, x) আর count_range(a, x1, x2) — শুধু bounds-এর সংযোজন-বিয়োগ; invariant comment লিখতে ভুলবেন না। ২. Rotated array-তে duplicates allowed version — worst case O(n)-এ নেমে আসে কেন (lo==mid==hi ambiguity) প্রমাণ করুন test-এ। ৩. bisect.insort benchmark: 10⁵ insertions-এ insort (O(n) shift প্রতিটায়) vs append+final sort — amortized cost মেপে surprise দেখুন (hint: locality আবার কথা বলে)।