Modified Binary Search Patterns

1. Search in 2D Matrix (Binary Search)

Matrix Type	Strategy	Complexity	Key Insight
Fully Sorted	Treat as 1D array, use binary search with index mapping	`O(log(m×n))`	map index i to [i/n][i%n]
Row & Column Sorted	Start from top-right or bottom-left, eliminate row or column	`O(m + n)`	Staircase search pattern
Row Sorted Only	Binary search on each row	`O(m log n)`	m independent searches
First Column Sorted	Binary search rows, then binary search within row	`O(log m + log n)`	Two-level binary search

Example: Search in fully sorted 2D matrix

function searchMatrix(matrix, target) {
    if (!matrix.length || !matrix[0].length) {
        return false;
    }
    
    const m = matrix.length;
    const n = matrix[0].length;
    let left = 0;
    let right = m * n - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        // Convert 1D index to 2D coordinates
        const row = Math.floor(mid / n);
        const col = mid % n;
        const midVal = matrix[row][col];
        
        if (midVal === target) {
            return true;
        } else if (midVal < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return false;
}

// Matrix: [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
// Treat as: [1,3,5,7,10,11,16,20,23,30,34,60]

Example: Search in row/col sorted matrix

function searchMatrixII(matrix, target) {
    if (!matrix.length || !matrix[0].length) {
        return false;
    }
    
    const m = matrix.length;
    const n = matrix[0].length;
    
    // Start from top-right corner
    let row = 0;
    let col = n - 1;
    
    while (row < m && col >= 0) {
        const val = matrix[row][col];
        
        if (val === target) {
            return true;
        } else if (val > target) {
            col--; // Move left (smaller values)
        } else {
            row++; // Move down (larger values)
        }
    }
    
    return false;
}

// Matrix: [[1,4,7,11],[2,5,8,12],[3,6,9,16]]
// Each row sorted, each column sorted
// Staircase search from top-right

2. Find Peak Element Problem

Property	Technique	Condition	Guarantee
Peak Definition	Element greater than neighbors	`nums[i] > nums[i-1] && nums[i] > nums[i+1]`	At least one peak exists
Binary Search	Move toward higher neighbor	If `nums[mid] < nums[mid+1]`, go right	Always converges to peak
Edge Cases	Treat out-of-bounds as -∞	First/last elements can be peaks	No special handling needed
Multiple Peaks	Any peak is valid answer	Binary search finds one peak	O(log n) solution

Example: Find peak element

function findPeakElement(nums) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        
        // Compare with right neighbor
        if (nums[mid] < nums[mid + 1]) {
            // Peak is on the right (ascending)
            left = mid + 1;
        } else {
            // Peak is on the left or at mid (descending)
            right = mid;
        }
    }
    
    return left; // or right, they're equal
}

// Example: [1,2,3,1] -> return 2 (index of peak 3)
// Example: [1,2,1,3,5,6,4] -> return 1 or 5

// Why this works:
// - If mid < mid+1, peak must be on right (we're ascending)
// - If mid > mid+1, peak could be mid or on left
// - Loop terminates when left === right (found peak)

Note: Peak finding works because: if we're at position where right neighbor is higher, moving right guarantees we'll reach a peak (either continues ascending to end, or descends at some point creating a peak).

3. Search in Rotated Sorted Array

Scenario	Identification	Action	Example
Left Half Sorted	`nums[left] <= nums[mid]`	Check if target in sorted half, else search other half	[4,5,6,7,0,1,2] mid=7
Right Half Sorted	`nums[mid] < nums[right]`	Check if target in sorted half, else search other half	[4,5,6,7,0,1,2] mid=0
Target in Sorted Half	Compare target with boundaries	Binary search in that half	Target=5 in [4,5,6,7]
Target in Unsorted Half	Other half must contain rotation	Search in unsorted half	Target=1 in [0,1,2]

Example: Search in rotated sorted array

function searchRotated(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 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]) {
                // Target in left sorted half
                right = mid - 1;
            } else {
                // Target in right half
                left = mid + 1;
            }
        } else {
            // Right half is sorted
            if (nums[mid] < target && target <= nums[right]) {
                // Target in right sorted half
                left = mid + 1;
            } else {
                // Target in left half
                right = mid - 1;
            }
        }
    }
    
    return -1;
}

// Example: nums = [4,5,6,7,0,1,2], target = 0
// Output: 4
// Rotation point between 7 and 0

4. Find Minimum in Rotated Sorted Array

Pattern	Condition	Decision	Invariant
No Rotation	`nums[left] < nums[right]`	Return nums[left]	Already sorted
Mid in Left Part	`nums[mid] > nums[right]`	Minimum in right half: `left = mid + 1`	Rotation point on right
Mid in Right Part	`nums[mid] <= nums[right]`	Minimum in left half or at mid: `right = mid`	Rotation point on left or mid
With Duplicates	`nums[mid] === nums[right]`	Shrink: `right--`	Worst case O(n)

Example: Find minimum (no duplicates)

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

// Example: [3,4,5,1,2] -> 1
// Example: [4,5,6,7,0,1,2] -> 0
// Example: [11,13,15,17] -> 11 (no rotation)

Example: Find minimum (with duplicates)

function findMinDuplicates(nums) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        
        if (nums[mid] > nums[right]) {
            // Min is in right half
            left = mid + 1;
        } else if (nums[mid] < nums[right]) {
            // Min is in left half or at mid
            right = mid;
        } else {
            // nums[mid] === nums[right]
            // Can't determine which half, shrink right
            right--;
        }
    }
    
    return nums[left];
}

// Example: [2,2,2,0,1] -> 0
// Example: [1,3,5] -> 1
// Duplicates require O(n) worst case

5. Search Insert Position in Array

Variant	Return Value	Condition	Use Case
Insert Position	Index where target should be inserted	First position where `nums[i] >= target`	Maintain sorted order
Lower Bound	First occurrence of target	Leftmost position with `nums[i] >= target`	Find start of range
Upper Bound	First element greater than target	Leftmost position with `nums[i] > target`	Find end of range + 1
Exact Match	Index if found, -1 otherwise	Traditional binary search	Element lookup

Example: Search insert position (lower bound)

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

// Example: nums = [1,3,5,6], target = 5 -> 2
// Example: nums = [1,3,5,6], target = 2 -> 1
// Example: nums = [1,3,5,6], target = 7 -> 4
// Example: nums = [1,3,5,6], target = 0 -> 0

// Pattern: Find leftmost position where nums[i] >= target
// If target exists, returns its first occurrence
// If target doesn't exist, returns where it should be inserted

Example: Lower and upper bound templates

// Lower bound: first position where nums[i] >= target
function lowerBound(nums, target) {
    let left = 0;
    let right = nums.length;
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

// Upper bound: first position where nums[i] > target
function upperBound(nums, target) {
    let left = 0;
    let right = nums.length;
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

// Usage examples:
const nums = [1, 2, 2, 2, 3, 4, 5];
console.log(lowerBound(nums, 2)); // 1 (first 2)
console.log(upperBound(nums, 2)); // 4 (first element > 2)
// Range of 2's: [lowerBound, upperBound)

6. Find First and Last Position in Sorted Array

Task	Approach	Technique	Complexity
Find First	Binary search for leftmost occurrence	When found, continue searching left	`O(log n)`
Find Last	Binary search for rightmost occurrence	When found, continue searching right	`O(log n)`
Two Binary Searches	Run two independent searches	Lower bound and upper bound - 1	`O(log n)`
No Match	Return [-1, -1]	Check if target exists at found position	Handle edge case

Example: Find first and last position

function searchRange(nums, target) {
    const first = findFirst(nums, target);
    const last = findLast(nums, target);
    return [first, last];
}

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

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

// Example: nums = [5,7,7,8,8,10], target = 8
// Output: [3, 4]
// Example: nums = [5,7,7,8,8,10], target = 6
// Output: [-1, -1]

Example: Using lower/upper bound approach

function searchRangeBounds(nums, target) {
    const left = lowerBound(nums, target);
    const right = upperBound(nums, target) - 1;
    
    // Check if target exists
    if (left < nums.length && nums[left] === target) {
        return [left, right];
    }
    return [-1, -1];
}

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

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

// Cleaner approach using standard bound functions
// First = lowerBound, Last = upperBound - 1

Warning: Common binary search pitfalls:

Infinite loop: Use left < right vs left <= right appropriately based on loop variant
Overflow: Use left + Math.floor((right - left) / 2) instead of (left + right) / 2
Off-by-one: Carefully choose mid + 1 or mid - 1 vs mid
Boundary conditions: Test with empty array, single element, duplicates, target at edges

Summary: Modified Binary Search Patterns

2D Matrix Search: Fully sorted treats as 1D with index mapping; row/col sorted uses staircase from top-right O(m+n)
Peak Element: Move toward higher neighbor - if mid < mid+1 go right, else go left; always converges to peak O(log n)
Rotated Array Search: Determine which half is sorted (nums[left] ≤ nums[mid] or nums[mid] < nums[right]), check if target in sorted half
Find Minimum Rotated: If nums[mid] > nums[right], minimum in right half; else minimum in left or at mid; O(log n)
Duplicates in Rotated: When nums[mid] == nums[right], must shrink right-- resulting in worst case O(n)
Insert Position: Lower bound pattern - first position where nums[i] ≥ target using left < right loop
Lower/Upper Bound: Lower: first ≥ target; Upper: first > target; use right = nums.length to handle insertion at end
First/Last Position: Two binary searches: find first by continuing left when found, find last by continuing right when found
Bounds Alternative: First position = lowerBound, Last position = upperBound - 1, check if target exists
Loop Variants: left < right with right = mid or left <= right with right = mid - 1 - be consistent
Key Principle: Maintain invariant that answer is always in [left, right], eliminate half of search space each iteration

Related Cheat Sheets

Datastructures Algorithms