Quick Overview
A linear scan checks every element. Halving the search space each step turns 1,000,000 candidates into roughly 20 comparisons, but only because the data is already sorted.
Searching an element linearly in an array of 1,000,000 items takes up to 1,000,000 comparisons. Binary Search cuts the search space in half at every step, finding any element in at most 20 comparisons (log_2(1,000,000) ≈ 20)!
function binarySearch(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
// Avoid integer overflow: Math.floor(left + (right - left) / 2)
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
return mid; // Found target index!
} else if (nums[mid] < target) {
left = mid + 1; // Target is in the right half
} else {
right = mid - 1; // Target is in the left half
}
}
return -1; // Target not found
}
console.log(binarySearch([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 23)); // Output: 5
Find the first position where target can be inserted while maintaining sorted order:
function bisectLeft(nums, target) {
let left = 0;
let right = nums.length;
while (left < right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid; // Narrow right bound
}
}
return left; // First index where nums[index] >= target
}
console.log(bisectLeft([1, 2, 4, 4, 4, 6, 7], 4)); // Output: 2 (First occurrence of 4)
(left + right) / 2 can overflow 32-bit signed integers in languages like Java, C++, and Go when left + right > 2^31 - 1. Use left + (right - left) / 2.left = mid instead of left = mid + 1 can freeze the loop when left and right are adjacent.Binary search applies to any monotonic search space. Next, let's explore Merge Sort and Quick Sort!
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.