Binary Search · LC #704
Binary Search
Given a sorted array of distinct integers and a target value, return the index of the target using O(log n) binary search, or -1 if not found.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given a sorted array of distinct integers `nums` and an integer `target`, return the index of `target` within `nums`, or `-1` if it does not exist. You must write an algorithm with O(log n) runtime complexity.
Sample I/O
Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1
Time: O(log n) · Space: O(1)
Intuition
How to Think About It
Intuition
Because the array is sorted, we can eliminate half the remaining candidates at every step by comparing the middle element to the target - the classic divide-and-conquer insight that drives O(log n) search.
Core Concept
Maintain two pointers `l` and `r` bounding the live search space. Each iteration computes `mid = l + (r-l)/2`, compares `nums[mid]` to target, and either returns mid or shrinks the window by setting `l = mid+1` or `r = mid-1`. The invariant is: if target exists it is always within `[l, r]`. The loop exits when `l > r` (target absent).
When to use
Use when the input is sorted (or monotone) and you need O(log n) lookup, or when you can reformulate the answer space as a monotone predicate.
When NOT to use
Avoid when the collection is unsorted and sorting would dominate cost, or when the data structure does not support O(1) random access (e.g. linked lists).
Key Insights
What to Know Cold
- Compute mid as `l + (r-l)/2` not `(l+r)/2` to prevent integer overflow in Java/C++.
- Loop condition is `l <= r` (inclusive bounds) - loop body can return early on a hit.
- On miss, `l` ends up pointing to the insertion position (useful for Search Insert Position).
- Every iteration the window halves, so at most ⌈log₂ n⌉ + 1 iterations are needed.
- Works on any strictly-monotone predicate, not just equality - the foundation of "binary search on answer" patterns.
3 examples
Worked Examples
Standard sorted array lookup
Search for target=9 in [-1,0,3,5,9,12].
l=0, r=5. mid=2 → nums[2]=3 < 9 → l=3. mid=4 → nums[4]=9 == target → return 4.
function search(nums: number[], target: number): number {
let l = 0, r = nums.length - 1;
while (l <= r) {
const mid = l + Math.floor((r - l) / 2);
if (nums[mid] === target) return mid;
else if (nums[mid] < target) l = mid + 1;
else r = mid - 1;
}
return -1;
}Output: 4
Baseline template; every binary-search variant builds on this pattern.
Target absent
Search for target=2 in [-1,0,3,5,9,12].
l=0, r=5. mid=2 → 3 > 2 → r=1. mid=0 → -1 < 2 → l=1. mid=1 → 0 < 2 → l=2. l > r → return -1.
Validates that the loop terminates correctly on a miss with `l > r`.
Single-element array
nums=[5], target=5.
l=0, r=0. mid=0. nums[0]==5 → return 0.
Edge case: search space starts and ends at the same index.