Interview OS
Back to Algorithms & Data Structures

Library

Binary search & variants

Search on sorted data or answer space.

Search

Overview

Binary search repeatedly halves a monotonic search space for O(log n) results. Beyond sorted arrays, the 'search on the answer' pattern applies to any yes/no predicate that's monotonic over a range.

How it works

Search
InputBoundsHalveOutputSortedsortedlo / hilo,himidO(log n)Index
ClientServiceEdgeData

Step by step, with examples

  1. 1

    Sorted

    • A monotonic predicate over the range.
  2. 2

    lo / hi

    • Initialize the search range.
  3. 3

    mid

    • Discard half each iteration.
  4. 4

    Index

    • Return the index or boundary.
    • Example: lower_bound

Overview

Halve a monotonic search space each step — including 'binary search on the answer' for optimization problems.

Reference

// smallest x in [lo,hi] with feasible(x)
function bs(lo,hi,feasible){ while(lo<hi){ const m=(lo+hi)>>1; feasible(m)?hi=m:lo=m+1; } return lo; }

Common pitfalls

  • Bad mid update -> infinite loop
  • Inclusive vs exclusive bounds

Where this content comes from

For full transparency, this content is curated and verified from these sources:

CLRS — Introduction to AlgorithmsCurated competitive-programming archivesOppZen-authored algorithm guides