Binary Search in JavaScript: O(log n) Search Explained
Imagine searching for a word in a dictionary by opening to the exact middle, then jumping to the middle of whichever half remains. That's binary search. A 1,000,000-element sorted array needs at most 20 comparisons. A linear search of the same array needs up to 1,000,000. Binary search is one of the most important algorithms in computer science — it appears in interviews, library code, and operating systems. The prerequisite: the array must be sorted.
How It Works: The Core Idea
Maintain two pointers, left and right, defining the current search window. At each step, check the middle element:
- If it equals the target → return the index.
- If it's less than the target → target must be right; move
leftup. - If it's greater → target must be left; move
rightdown.
Repeat until found, or until left > right (window empty).
Step-by-Step Walkthrough
// nums = [1, 2, 4, 5, 7, 9, 12], value = 7
// 0 1 2 3 4 5 6
// Step 1: left=0, right=6, mid=3 → nums[3]=5 < 7 → search right half
// Step 2: left=4, right=6, mid=5 → nums[5]=9 > 7 → search left half
// Step 3: left=4, right=4, mid=4 → nums[4]=7 == 7 → FOUND at index 4
3 comparisons instead of potentially 7 for linear search. At scale, this difference is enormous.
Code Implementation
function binarySearch(nums, value) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === value) {
return mid; // found — return the index
} else if (nums[mid] < value) {
left = mid + 1; // target is in the right half
} else {
right = mid - 1; // target is in the left half
}
}
return -1; // target not in array
}
console.log(binarySearch([1, 2, 4, 5], 4)); // 2
console.log(binarySearch([1, 2, 4, 5], 3)); // -1
console.log(binarySearch([1, 3, 5, 7, 9], 1)); // 0 (first element)
console.log(binarySearch([1, 3, 5, 7, 9], 9)); // 4 (last element)
Complexity Analysis
- Time: O(log n) — the search space halves with each comparison. 1 billion elements → at most 30 comparisons.
- Space: O(1) — only two pointers, no extra data regardless of array size.
Critical Pitfalls to Avoid
while (left < right)vswhile (left <= right): Use<=. A strict<misses the single-element window (left === right), causing false negatives.- Off-by-one in pointer updates: Always use
mid + 1andmid - 1— never justmid. Forgetting the ±1 creates an infinite loop. - Applying binary search to unsorted data: It only works on sorted arrays. Check your input.
Edge Cases
console.log(binarySearch([], 5)); // -1 (empty array)
console.log(binarySearch([7], 7)); // 0 (single element, found)
console.log(binarySearch([7], 3)); // -1 (single element, not found)
console.log(binarySearch([1, 3, 5, 7], 1)); // 0 (first position)
console.log(binarySearch([1, 3, 5, 7], 7)); // 3 (last position)
console.log(binarySearch([1, 3, 5, 7], 4)); // -1 (not present)
Key Takeaways
- Binary search requires a sorted array and finds any value in O(log n) time.
- Use
while (left <= right)and update withleft = mid + 1/right = mid - 1. - Return
-1when the loop ends without finding the target. - Space is O(1) — no recursion, no extra data structures.
What to Learn Next
Iterative binary search is the foundation. Next, implement the recursive version to understand how the same logic looks with call stacks instead of a loop. Then explore powerful variations: finding the first or last occurrence of a duplicate value, searching a rotated sorted array, and binary search on the answer — where you binary search over a range of possible answers rather than an array of data.
