Binary Search: Standard & Bisect Boundaries
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.
Deep Dive
1. Divide and Conquer in O(log N)
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)!
2. Standard Binary Search Template
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
3. Bisect Left (Lower Bound)
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)
4. Common Mistakes
- Integer Overflow in Mid Calculation: Writing
(left + right) / 2can overflow 32-bit signed integers in languages like Java, C++, and Go whenleft + right > 2^31 - 1. Useleft + (right - left) / 2. - Infinite Loops from Improper Pointer Updates: Setting
left = midinstead ofleft = mid + 1can freeze the loop whenleftandrightare adjacent.
5. Next Steps
Binary search applies to any monotonic search space. Next, let's explore Merge Sort and Quick Sort!
Next Up in Data Structures & Algorithms Core Patterns
Big O Notation: Time & Space Complexity
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.
Dynamic Arrays & Amortized Resizing
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.
Two Pointers Pattern (Converging & Symmetrical)
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.