Mastering Binary Search

Binary Search is a divide-and-conquer strategy that finds the position of a target value within a sorted collection. By dividing the search interval in half on each step, we achieve logarithmic O(log N) time complexity.

Search on Answer Space (Optimization Problems)

Binary search can be applied to non-array inputs where the answer space is monotonic (i.e., if x is possible, all values > x are also possible). Examples include finding the minimum speed required to eat bananas or the minimum capacity to ship cargo.

function shipWithinDays(weights, days) {
    let left = Math.max(...weights);
    let right = weights.reduce((a, b) => a + b, 0);
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canShip(weights, days, mid)) {
            right = mid; // Try smaller capacity
        } else {
            left = mid + 1; // Increase capacity
        }
    }
    return left;
}

Common Boundaries Mistakes

• Avoid integer overflow when calculating midpoint: use left + Math.floor((right - left) / 2).
• Ensure loop terminates: be careful with while (left <= right) vs while (left < right).
• Verify bounds shift: always update pointers with mid + 1 or mid - 1 to prevent infinite loops.