Binary Search
easyTime: O(log n)Space: O(1)
The shape of the problem
Given a sorted array and a target, return the index of the target or -1 if absent. Must run in O(log n).
Signals to notice
sorted arraytarget lookuphalve the search space each step
Brute force first
Linear scan from index 0 to the target. O(n) and ignores the sorted property.
The key insight
A sorted array tells you, at any midpoint, whether the target is to the left, right, or here. That lets each step discard half of the remaining positions.
Trace it on nums=[-1,0,3,5,9,12], target=9
lo=0 hi=5 mid=2 nums[2]=3 3 < 9 → lo=3 lo=3 hi=5 mid=4 nums[4]=9 9 == 9 → return 4
What must stay true
If the target exists, it lives in `nums[lo..hi]`. The window strictly shrinks every iteration.
Shape of the loop
lo, hi = 0, n-1 while lo <= hi: mid = lo + (hi - lo) // 2 if nums[mid] == target: return mid elif nums[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Using `(lo + hi) / 2` in languages where `lo + hi` can overflow a 32-bit integer. Use `lo + (hi - lo) / 2` instead.