Framework #9 — Binary search boundary template

Three binary search templates: exact match (lo<=hi), boundary finding (lo<hi), and search-on-answer (feasible predicate). Pick by problem type.

BINARY SEARCH — BOUNDARY DECISION
──────────────────────────────────
FIND EXACT VALUE:
  while lo &lt;= hi:
      mid = (lo + hi) // 2
      if a[mid] == target: return mid
      elif a[mid] &lt; target: lo = mid + 1
      else: hi = mid - 1
  return -1

FIND FIRST &gt;= target (leftmost):
  while lo &lt; hi:
      mid = (lo + hi) // 2
      if a[mid] &lt; target: lo = mid + 1
      else: hi = mid
  return lo  # first position &gt;= target

FIND LAST &lt;= target (rightmost):
  while lo &lt; hi:
      mid = (lo + hi + 1) // 2   # round UP
      if a[mid] &gt; target: hi = mid - 1
      else: lo = mid
  return lo  # last position &lt;= target

SEARCH ON ANSWER (min satisfying):
  lo, hi = min_ans, max_ans
  while lo &lt; hi:
      mid = (lo + hi) // 2
      if feasible(mid): hi = mid
      else: lo = mid + 1
  return lo

DECISION:
  Exact match?    → lo &lt;= hi, 3-way branch
  First/last pos? → lo &lt; hi, 2-way converge
  Min feasible?   → lo &lt; hi, feasible() predicate

Framework #9 — Binary search boundary template

Practice Problems