Interview preparation
Binary Search
1Problem statement
Given a sorted (ascending) array of distinct integers nums and a target, return the index of target, or −1 if it is not present. Your algorithm must run in O(log n) time.
2Examples
3Constraints
- 1 ≤ nums.length ≤ 10⁴
- All values are unique and sorted ascending.
4Approaches
Approach 1
Brute Force
Linear scan comparing each element with target.
Approach 2
Better: Recursive binary search
Recurse into the half that can contain the target.
Approach 3
Optimal: Iterative binary search
Maintain [low, high]; compare with mid and discard half of the range each iteration.
5Code (optimal approach)
Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.
function search(nums, target) {
let low = 0;
let high = nums.length - 1;
while (low <= high) {
const mid = low + Math.floor((high - low) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}
console.log(search([-1, 0, 3, 5, 9, 12], 9));
console.log(search([-1, 0, 3, 5, 9, 12], 2));
6Complexity
Time
O(log n)
Space
O(1)
7Visual walkthrough
Step through this exact algorithm:
Searches a sorted array by repeatedly comparing the target with the middle element and discarding the half that cannot contain it.