Skip to content
ComplexityX

Settings

Server engine

Loading…

Use my own key optional

The key stays in this browser's local storage and is sent only to this app's /api/analyze route, which forwards it to the provider. It is never stored on the server.

All patterns

Binary Search

Halve the search space using a monotone yes/no question.

time O(log n) × cost of checkspace O(1)

What it is

If a predicate flips from false to true exactly once across a range, you can find the flip point in O(log n). It works on sorted arrays and also on answer spaces such as “smallest capacity that works”.

When to reach for it

  • Sorted or rotated sorted data
  • Minimize the maximum or maximize the minimum
  • Find the first index satisfying a condition

Clues in the problem

  • Target complexity O(log n)
  • A feasibility check that is monotone in the answer
  • n up to 10⁹ or more

Template

def first_true(lo, hi, ok):
# smallest x in [lo, hi] with ok(x) True; ok is monotone
while lo < hi:
mid = lo + (hi - lo) // 2 # avoids overflow
if ok(mid):
hi = mid
else:
lo = mid + 1
return lo

Practice problems

  • Search in Rotated Sorted Array
  • Koko Eating Bananas
  • Capacity To Ship Packages
  • Find First and Last Position

Common mistakes

  • (lo + hi) / 2 overflow in Java or C++
  • Infinite loop from lo = mid when mid == lo
  • Applying it when the predicate is not monotone