Binary Search — Binary Search
↗ LeetCode: Binary Search · Easy · pattern chapter →
Given a sorted array nums and an integer target, return the index of target, or -1 if not present. Must run in O(log n) time.
Example 1 — nums = [-1,0,3,5,9,12], target = 9 → 4Example 2 — nums = [-1,0,3,5,9,12], target = 2 → -1Example 3 — nums = [5], target = 5 → 0
Constraints — 1 ≤ n ≤ 10⁴; all distinct; sorted ascending. Brute linear scan is O(n) — 10⁴ ops per query, dies with 10⁵ queries. Binary search is O(log n) = 14 comparisons even at n=10⁴; 30 comparisons at n=10⁹.
Interview timer00:00
Approach 1 — Linear scan
O(n) time. Rejected by spec.
Approach 2 — Standard binary search (closed interval)
Intuition. Maintain [lo, hi] as the still-possible range. Look at mid; discard one half.
Trap — use lo + (hi - lo) / 2 to avoid integer overflow when lo + hi overflows.
int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}Complexity — Time O(log n); Space O(1).
Approach 3 — Half-open convention ([lo, hi)) — safer for boundary problems
Insight. Using hi = nums.length (one past the end) and lo < hi avoids off-by-one errors when generalizing to "first true" / "last false" problems.
int searchHO(int[] nums, int target) {
int lo = 0, hi = nums.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < target) lo = mid + 1;
else hi = mid;
}
return (lo < nums.length && nums[lo] == target) ? lo : -1;
}Why this template. After the loop, lo is the smallest index with nums[lo] ≥ target (lower_bound). Widely reusable for Search Insert Position, first-occurrence, etc.
Complexity — Time O(log n); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Linear scan | O(n) | O(1) | rejected |
| Closed-interval BS | O(log n) | O(1) | expected |
| Half-open BS | O(log n) | O(1) | polish — extensible template |
When to use which
- Presence check on sorted array → either template works.
- Search-insert / lower_bound / upper_bound → half-open template is cleaner.
- Rotated sorted array → see Search in Rotated Sorted Array.
- Binary search on the answer → apply the same template with a feasibility predicate; see Koko Eating Bananas.
Related problems
- Search Insert Position — lower_bound
- First Bad Version — "first true"
- Search in Rotated Sorted Array — piecewise-sorted
- Find Peak Element — BS on non-monotone