LeetCode Search a 2D Matrix：二維有序矩陣二分查找

問題描述

給定 m×n 矩陣，每行遞增，每行首元素大於上行尾元素。判斷目標值是否存在。要求高效算法。

一維二分映射到二維

將矩陣視為長度 m*n 的有序數組。二分索引 mid，映射為二維座標：

row = mid / n;
col = mid % n;

比較 matrix[row][col] 與目標值，調整二分邊界。

代碼實現

class Solution {
public:
    bool searchMatrix(const vector>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int m = matrix.size(), n = matrix[0].size();
        int lo = 0, hi = m * n;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int r = mid / n, c = mid % n;
            if (matrix[r][c] == target) return true;
            else if (matrix[r][c] < target) lo = mid + 1;
            else hi = mid;
        }
        return false;
    }
};

複雜度

• 時間 O(log(mn))，空間 O(1)。

關鍵點

1. 嚴格有序性：題目條件保證扁平化後完全有序，可直接套用標準二分。
2. 索引映射：/ n 和 % n 無開銷。
3. 邊界：hi = m*n（開區間），lo < hi 循環，避免溢出用 lo + (hi-lo)/2。

本題是二分查找在二維矩陣上的直接應用，展示了「將多維有序結構線性化」的通用技巧。