Binary Search in Matrices: Ordered Matrix Search

Challenges involving 2D ordered matrices and "Kth Smallest" problems can often be solved efficiently using binary search variants.

Search a 2D Matrix (LeetCode 74)

In this problem, the matrix is sorted horizontally, and the last element of a row is smaller than the first element of the next row (global sortedness).

Strategy: Treat the matrix as a flattened 1D array. Use mid / columns and mid % columns to map indices back to 2D coordinates.

public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    int low = 0, high = m * n - 1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        // Map 1D index to 2D row/col
        int val = matrix[mid / n][mid % n];
        
        if (val == target) return true;
        else if (val < target) low = mid + 1;
        else high = mid - 1;
    }
    return false;
}

Search a 2D Matrix II (LeetCode 240)

Here, each row is sorted left-to-right and each column is sorted top-to-bottom, but there is no global connectivity between rows.

Strategy: Start from the top-right corner. This position acts like a "pivot" in a Binary Search Tree (left is smaller, down is larger).

public boolean searchMatrix(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--; // Search smaller values in the current row
        } else {
            row++; // Search larger values in the current column
        }
    }
    return false;
}

Note: Complexity is $O(M + N)$. While technically a "staircase search" rather than pure binary search, it's the standard optimal approach.

Kth Smallest Element in a Sorted Matrix (LeetCode 378)

Both rows and columns are sorted. Find the $k$-th smallest element.

Strategy: Binary search on the value range $[matrix[0][0], matrix[last][last]]$. For each mid value, count how many elements are $\le mid$.

public int kthSmallest(int[][] matrix, int k) {
    int n = matrix.length;
    int low = matrix[0][0], high = matrix[n - 1][n - 1];
    
    while (low < high) {
        int mid = low + (high - low) / 2;
        int count = countLessEqual(matrix, mid);
        if (count < k) {
            low = mid + 1; // Range of valid K elements is to the right
        } else {
            high = mid;    // mid could be the kth element
        }
    }
    return low;
}

// Counts elements <= mid in O(N) using the top-right/bottom-left trick
private int countLessEqual(int[][] matrix, int mid) {
    int n = matrix.length;
    int count = 0, row = n - 1, col = 0;
    while (row >= 0 && col < n) {
        if (matrix[row][col] <= mid) {
            count += row + 1; // All elements above this in the same column are also <= mid
            col++;
        } else {
            row--;
        }
    }
    return count;
}

Median of Two Sorted Arrays (LeetCode 4)

Find the median of two sorted arrays in $O(\log(min(M, N)))$ time.

Core Concept: Binary search on the partition point of the shorter array such that the combined "left half" has elements strictly smaller than the combined "right half."

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
    int m = nums1.length, n = nums2.length;
    int low = 0, high = m;
    
    while (low <= high) {
        int i = low + (high - low) / 2;
        int j = (m + n + 1) / 2 - i;
        
        int maxL1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
        int minR1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
        int maxL2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
        int minR2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
        
        if (maxL1 <= minR2 && maxL2 <= minR1) {
            if ((m + n) % 2 == 1) return Math.max(maxL1, maxL2);
            return (Math.max(maxL1, maxL2) + Math.min(minR1, minR2)) / 2.0;
        } else if (maxL1 > minR2) {
            high = i - 1;
        } else {
            low = i + 1;
        }
    }
    return 0.0;
}

Summary Selection Guide