#704
Binary Search
Easy Classic binary search
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Find the index of target in a sorted array, or return -1, in O(log n).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: find target in a sorted array in O(log n).
Why this works: compare with the middle; the target can only be in one half.
Example: [-1, 0, 3, 5, 9, 12], target 9
lo 0, hi 5 → mid 2 (3) < 9 → lo 3mid 4 (9) ✓ → index 4
✦Hints open one at a time
Compare with the middle element and throw away half.
Use mid = lo + (hi - lo) / 2 to avoid overflow.
↗Approach
Keep lo and hi as the inclusive search range. If nums[mid] is the target, return it; if smaller, search right; otherwise search left.
</>Solution (Java)
class Solution {
public 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;
}
}!Common mistake
Writing lo = mid instead of lo = mid + 1, which can loop forever.
Complexity
- Time: O(log n).
- Space: O(1).
Topic: Binary Search
🎬 Episodes 21–23: video coming soon