NOTE
Binary Search
Logarithmic search over a monotonic/sorted domain, including boundary variants.
This is a historical learning note and may contain outdated or incomplete understanding.
Binary search repeatedly halves a sorted or monotonic search space, giving O(log n) comparisons.
The hardest part is usually boundary semantics: exact match, first/last equal, first >= target, or last <= target. Define an invariant and whether the interval is closed/open before writing the loop.
Compute midpoint without overflow in fixed-width languages using low + (high-low)/2 or the language’s safe equivalent.