Binary Search
Divide search space in half — sorted arrays, answer space, and rotated arrays
0/32 solved
Search in Sorted Array
Classic binary search on a monotonically sorted array
Approach
Set left = 0, right = n-1. Compute mid. If target found, return. If target < mid, search left half. If target > mid, search right half. Repeat until left > right.
How to Recognize
Array is sorted (ascending or descending) — this is the #1 signal for binary search
Need O(log n) search for a target in a sorted collection
Keywords: 'find element in sorted array', 'search insert position', 'sqrt(x)'
Any problem where you can eliminate half the search space with one comparison
2D sorted matrix: treat as a 1D sorted array with index mapping (row = idx/cols, col = idx%cols)
Problem constraints say n ≤ 10^5 or 10^6 with O(log n) expected — binary search
You need to find a 'boundary' or 'insertion point' rather than exact match
Pro Tips
Use `left + (right - left) / 2` instead of `(left + right) / 2` to prevent integer overflow
Decide carefully: `left <= right` (inclusive) vs `left < right` (exclusive) — affects termination and return value
For lower bound: when target is found, DON'T return — set right = mid to keep narrowing left
For upper bound: when target is found, set left = mid + 1 to find the position after the last occurrence
Common bug: infinite loop when `left < right` and `mid = left + (right - left) / 2` with `left = mid` — use `mid = left + (right - left + 1) / 2` instead
For 'search insert position', the answer is simply the lower_bound — where target would be inserted
8
Total
6
Easy
2
Medium
0
Hard
Time
O(log n)
Space
O(1)