Binary Search Variations

Variations include real-valued binary search on doubles, discrete on integers, and parametric search sketches. Students should master integer templates first.

Try this in Python

def sqrt_int_floor(n: int) -> int:
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if mid * mid <= n:
            lo = mid
        else:
            hi = mid - 1
    return lo


print(sqrt_int_floor(15))

Key takeaways

• For integers: watch overflow in mid*mid (use mid <= n // mid).
• For doubles: stop by iterations or epsilon.
• Same logic, different number type.