Binary Search
Understand the problem
You're given an integer array nums sorted in ascending order and an integer target. Find the index of target in the array. If it isn't there, return -1.
Example:
nums = [-1, 0, 3, 5, 9, 12], target = 9
output = 4 // nums[4] = 9
nums = [-1, 0, 3, 5, 9, 12], target = 2
output = -1 // 2 is not in the arrayBinary search halves the search space at every step — that's how it turns O(n) into O(log n).
It only works when the array is sorted.
Show the basic approach (slower)
O(n) time, O(1) spacefunction search(nums: number[], target: number): number {
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) return i
}
return -1
}Scans sequentially from start to end — it ignores the fact that the array is sorted.
With n=10⁶ elements, binary search needs ~20 steps instead of 10⁶.
Optimal solution
O(log n) time, O(1) spacefunction search(nums: number[], target: number): number {
let low = 0
let high = nums.length - 1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
if (nums[mid] === target) return mid
if (nums[mid] < target) low = mid + 1 // target is in the right half
else high = mid - 1 // target is in the left half
}
return -1
}The optimal approach: at each step, compare the middle element with the target and discard the half that can't contain it.
- After log₂(n) steps, the search space shrinks to zero.
- Use
Math.floor((low + high) / 2)instead of(low + high) >> 1to avoid integer overflow in other languages.
Step-by-step trace
1function search(nums: number[], target: number): number {2 let low = 03 let high = nums.length - 14 while (low <= high) {5 const mid = Math.floor((low + high) / 2)6 if (nums[mid] === target) return mid7 if (nums[mid] < target) low = mid + 1 // target is in the right half8 else high = mid - 1 // target is in the left half9 }10 return -111}Edge cases to remember
Single-element array — low=high=0, mid=0, exactly one comparison.
Target smaller than every element — high reaches -1 first, the loop ends, return -1.
Target larger than every element — low moves past high, return -1.
Empty array — high=-1 < low=0 from the start, the loop never runs, return -1.
Duplicate elements — the problem doesn't guarantee unique elements, but classic binary search returns just one arbitrary index.