Binary Search Patterns Series — Blog 4: 2D Matrix & Advanced Variants

1. Binary Search in Row-wise & Column-wise Sorted Matrix

Problem:
Matrix is sorted row-wise and column-wise. Search for a target in O(m+n) or O(log(m*n)).

Example:

matrix = [
  [1, 4, 7, 11],
  [2, 5, 8, 12],
  [3, 6, 9, 16]
]
target = 5 → Output: true

1.1 Flatten 2D Matrix to 1D

Treat the matrix as a 1D sorted array:

public boolean searchMatrix(int[][] matrix, int target) {
    int n = matrix.length;
    int m = matrix[0].length;

    int low = 0, high = n*m - 1;

    while (low <= high) {
        int mid = low + (high - low)/2;
        int val = matrix[mid/m][mid%m];

        if (val == target) return true;
        else if (val < target) low = mid + 1;
        else high = mid - 1;
    }
    return false;
}

Time Complexity: O(log(m*n))
Space Complexity: O(1)

1.2 Staircase Search (O(m+n))

Start from top-right corner:

public boolean searchMatrixStaircase(int[][] matrix, int target) {
    int row = 0, col = matrix[0].length - 1;

    while (row < matrix.length && col >= 0) {
        if (matrix[row][col] == target) return true;
        else if (matrix[row][col] > target) col--;
        else row++;
    }
    return false;
}

2. Search in Infinite / Unknown Size Array

Problem: Array size unknown. Find target in O(log n).

Approach:

Exponentially expand search range: low = 0, high = 1, 2, 4, 8... until arr[high] >= target.
Apply normal binary search in [low, high].

public int searchInfiniteArray(ArrayReader reader, int target) {
    int low = 0, high = 1;
    while (reader.get(high) < target) {
        low = high;
        high = high * 2;
    }
    return binarySearch(reader, low, high, target);
}

Note: ArrayReader.get(index) returns large value if out of bounds.

3. Ternary Search for Unimodal Functions

Problem: Function f(x) first increases then decreases. Find maximum value.

Template:

double left = 0, right = 1000;
while (right - left > 1e-6) {
    double mid1 = left + (right - left)/3;
    double mid2 = right - (right - left)/3;

    if (f(mid1) < f(mid2)) left = mid1;
    else right = mid2;
}
return f(left); // maximum value

Use Case: Optimization problems, like finding peak in mountain array or maximizing profit.

4. Edge Cases & Tips

For matrix search, always check matrix.length and matrix[0].length.
Infinite array search: ensure exponential expansion does not overflow integer.
Ternary search: stop condition depends on required precision.
2D to 1D mapping: row = mid / cols, col = mid % cols.