Binary Search Pattern

1. Classic Binary Search Template O(log n)

Template Type	Condition	Loop Invariant	Use Case
Standard Template	`while (left <= right)`	Search space includes both boundaries	Find exact target in sorted array
Left Bias	`while (left < right)`	Answer in [left, right), terminates at left	Find first position meeting condition
Right Bias	`while (left < right)` + `mid = left + ⌊(right-left+1)/2⌋`	Answer in (left, right], terminates at right	Find last position meeting condition
Mid Calculation	`mid = left + (right - left) / 2`	Prevents integer overflow	Always use this instead of (left+right)/2

Example: Classic binary search (find exact target)

function binarySearch(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;  // Search right half
        } else {
            right = mid - 1; // Search left half
        }
    }
    
    return -1; // Target not found
}

// Time: O(log n), Space: O(1)

Example: Recursive binary search

function binarySearchRecursive(nums, target, left = 0, right = nums.length - 1) {
    if (left > right) return -1;
    
    const mid = left + Math.floor((right - left) / 2);
    
    if (nums[mid] === target) return mid;
    
    if (nums[mid] < target) {
        return binarySearchRecursive(nums, target, mid + 1, right);
    } else {
        return binarySearchRecursive(nums, target, left, mid - 1);
    }
}

// Space: O(log n) due to recursion stack

2. Lower Bound and Upper Bound Implementation

Bound Type	Definition	Template	Result
Lower Bound	First index where `arr[i] >= target`	`while (left < right); if (arr[mid] < target) left = mid+1`	Leftmost position to insert target
Upper Bound	First index where `arr[i] > target`	`while (left < right); if (arr[mid] <= target) left = mid+1`	Rightmost position to insert target
First Occurrence	Leftmost index of target value	Lower bound with equality check	Start of range of equal values
Last Occurrence	Rightmost index of target value	Upper bound - 1 with equality check	End of range of equal values

Example: Lower bound (first >= target)

function lowerBound(nums, target) {
    let left = 0;
    let right = nums.length;
    
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid; // Could be answer
        }
    }
    
    return left;
}

// [1,2,4,4,5], target=4 -> 2
// [1,2,4,4,5], target=3 -> 2

Example: Upper bound (first > target)

function upperBound(nums, target) {
    let left = 0;
    let right = nums.length;
    
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}

// [1,2,4,4,5], target=4 -> 4
// [1,2,4,4,5], target=3 -> 2

Example: Find first and last position of element

function searchRange(nums, target) {
    const findFirst = () => {
        let left = 0, right = nums.length - 1;
        let result = -1;
        
        while (left <= right) {
            const mid = left + Math.floor((right - left) / 2);
            
            if (nums[mid] === target) {
                result = mid;
                right = mid - 1; // Keep searching left
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    };
    
    const findLast = () => {
        let left = 0, right = nums.length - 1;
        let result = -1;
        
        while (left <= right) {
            const mid = left + Math.floor((right - left) / 2);
            
            if (nums[mid] === target) {
                result = mid;
                left = mid + 1; // Keep searching right
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    };
    
    return [findFirst(), findLast()];
}

3. Search in Rotated Sorted Array

Variant	Key Insight	Strategy	Complexity
Rotated Sorted Array	One half always sorted	Identify sorted half, check if target in range	`O(log n)`
With Duplicates	May need to skip duplicates	When arr[left]=arr[mid]=arr[right], shrink linearly	`O(log n)` avg, `O(n)` worst
Find Minimum	Minimum at rotation point	Compare mid with right, move towards unsorted half	`O(log n)`
Rotation Count	Index of minimum element	Same as find minimum, return index	`O(log n)`

Example: Search in rotated sorted array

function searchRotated(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (nums[mid] === target) return mid;
        
        // Determine which half is sorted
        if (nums[left] <= nums[mid]) {
            // Left half is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1; // Target in left half
            } else {
                left = mid + 1;  // Target in right half
            }
        } else {
            // Right half is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;  // Target in right half
            } else {
                right = mid - 1; // Target in left half
            }
        }
    }
    
    return -1;
}

// [4,5,6,7,0,1,2], target=0 -> 4

Example: Find minimum in rotated sorted array

function findMin(nums) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (nums[mid] > nums[right]) {
            // Minimum is in right half
            left = mid + 1;
        } else {
            // Minimum is in left half or at mid
            right = mid;
        }
    }
    
    return nums[left];
}

// [3,4,5,1,2] -> 1
// [4,5,6,7,0,1,2] -> 0

4. Binary Search on Answer Space Pattern

Pattern	Problem Type	Search Space	Example Problems
Minimize Maximum	Find smallest value where condition holds	`[min_possible, max_possible]`	Split array largest sum, minimize max distance
Maximize Minimum	Find largest value where condition holds	`[min_possible, max_possible]`	Aggressive cows, maximize minimum distance
Feasibility Check	Binary search with validation function	Test if value is feasible	Koko eating bananas, capacity to ship packages
Monotonic Property	Answer space has monotone property	If k works, all values in direction also work	Essential for binary search applicability

Example: Koko eating bananas (minimize eating speed)

function minEatingSpeed(piles, h) {
    // Can Koko finish all piles in h hours at speed k?
    const canFinish = (k) => {
        let hours = 0;
        for (let pile of piles) {
            hours += Math.ceil(pile / k);
        }
        return hours <= h;
    };
    
    let left = 1; // Minimum speed
    let right = Math.max(...piles); // Maximum speed needed
    
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (canFinish(mid)) {
            right = mid; // Try slower speed
        } else {
            left = mid + 1; // Need faster speed
        }
    }
    
    return left;
}

// piles=[3,6,7,11], h=8 -> 4

Example: Capacity to ship packages within D days

function shipWithinDays(weights, days) {
    // Can ship all packages in 'days' with capacity 'cap'?
    const canShip = (capacity) => {
        let daysNeeded = 1;
        let currentWeight = 0;
        
        for (let weight of weights) {
            if (currentWeight + weight > capacity) {
                daysNeeded++;
                currentWeight = 0;
            }
            currentWeight += weight;
        }
        
        return daysNeeded <= days;
    };
    
    let left = Math.max(...weights); // Min capacity = max weight
    let right = weights.reduce((a, b) => a + b); // Max = sum all
    
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (canShip(mid)) {
            right = mid; // Try smaller capacity
        } else {
            left = mid + 1; // Need larger capacity
        }
    }
    
    return left;
}

5. Floating Point Binary Search Precision

Aspect	Integer Binary Search	Floating Point Binary Search
Termination	`left <= right`	`right - left > epsilon`
Precision	Exact integer values	Threshold like `1e-6` or `1e-9`
Iterations	`log₂(n)`	Fixed iterations (e.g., 100) or epsilon-based
Mid Update	`mid = (left + right) / 2`	`mid = (left + right) / 2.0`

Example: Square root with precision

function sqrt(x, precision = 1e-6) {
    if (x === 0) return 0;
    
    let left = 0;
    let right = x;
    
    // For x < 1, sqrt(x) > x
    if (x < 1) right = 1;
    
    while (right - left > precision) {
        const mid = (left + right) / 2;
        const square = mid * mid;
        
        if (square < x) {
            left = mid;
        } else {
            right = mid;
        }
    }
    
    return (left + right) / 2;
}

// sqrt(2) ≈ 1.414214
// sqrt(0.25) ≈ 0.5

Example: Find peak element with fixed iterations

function findPeakElement(nums) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (nums[mid] < nums[mid + 1]) {
            // Peak is on the right
            left = mid + 1;
        } else {
            // Peak is on the left or at mid
            right = mid;
        }
    }
    
    return left; // Peak index
}

// Works for integer arrays but demonstrates
// the concept of moving towards increasing direction

6. Binary Search Edge Cases and Debugging

Common Bug	Symptom	Fix	Prevention
Infinite Loop	Loop never terminates	Check mid calculation, ensure progress	Use `left + (right-left)/2`, verify bounds update
Off-by-One	Missing boundary elements	Review `<` vs `<=`, `mid±1`	Test with arrays of size 1, 2, 3
Integer Overflow	Incorrect mid for large arrays	Never use `(left+right)/2`	Always: `left + (right-left)/2`
Wrong Condition	Returns incorrect result	Clarify what you're searching for	Write invariant: what does [left,right] contain?

Note: Common mistakes to avoid:

Using (left + right) / 2 - causes overflow
Not maintaining loop invariant
Incorrect boundary updates (infinite loop)
Forgetting edge cases (empty array, single element)

Warning: Debug checklist:

Does loop make progress every iteration?
Are boundaries updated correctly?
Is mid calculation overflow-safe?
Test with edge cases: [1], [1,2], [1,2,3]

Example: Debugging template with invariant comments

function binarySearchWithInvariant(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    
    // Invariant: if target exists, it's in [left, right]
    while (left <= right) {
        // Prevent overflow
        const mid = left + Math.floor((right - left) / 2);
        
        if (nums[mid] === target) {
            return mid; // Found
        }
        
        // Maintain invariant: eliminate half that can't contain target
        if (nums[mid] < target) {
            left = mid + 1;  // Target must be in (mid, right]
        } else {
            right = mid - 1; // Target must be in [left, mid)
        }
    }
    
    // Invariant broken: target doesn't exist
    return -1;
}

Binary Search Pattern Summary

Classic Template: while(left<=right), mid = left+(right-left)/2
Lower Bound: First position >= target, while(left<right)
Answer Space: Binary search on result values with feasibility check
Rotated Array: Identify sorted half, check if target in range
Key Insight: Eliminate half of search space each iteration = O(log n)

Note: Binary search requires monotonic property - some characteristic that increases/decreases across the search space. This applies to sorted arrays (element values increase) and answer spaces (feasibility changes at a threshold).

Related Cheat Sheets

Algorithm Patterns