Part 2 · Problems · Binary search
Binary Search
#704 · Easy · LeetCode
Sorted array, return the index of target or -1.
[-1,0,3,5,9,12], 9 -> 4 [-1,0,3,5,9,12], 2 -> -1
Ask before coding
- Sorted ascending? Duplicates?
Hint
Compare with the middle, throw away half.
Approach
lo and hi bound the range. Check mid. Go right if mid is too small, left if too big. Stop when lo passes hi.
Time O(log n) Space O(1)
Watch it run
Solution (JavaScript, tested)
function search(nums, target) {
let lo = 0,
hi = nums.length - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}Traps
- Use lo <= hi with hi = n - 1. Mixing styles gives infinite loops.
- mid = lo + (hi - lo) / 2 avoids overflow in other languages.
Say out loud: Sorted input means binary search, log n. I'll use the inclusive version, lo <= hi.