LeetCode 搜索二維矩陣：從右上角出發的 O(m+n) 算法

LeetCode「搜索二維矩陣」要求在行遞增、且下一行首元素大於上一行尾元素的矩陣中查找目標值。本文介紹從右上角（或左下角）出發的線性掃描算法，時間複雜度 O(m+n)，空間 O(1)。

矩陣性質分析

• 每行從左到右遞增。
• 下一行第一個元素 > 上一行最後一個元素。
• 等價於：將矩陣展平為一維數組後整體有序。

兩種高效方法

方法一：二分查找（推薦）

視為有序數組，標準二分查找，時間 O(log(mn))，空間 O(1)。

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int l = 0, r = m * n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        int val = matrix[mid / n][mid % n];
        if (val == target) return true;
        else if (val < target) l = mid + 1;
        else r = mid - 1;
    }
    return false;
}

方法二：右上角線性掃描（原文方法）

從右上角 (0, n-1) 開始：

• 若當前值 == target → 找到。
• 若當前值 < target → 該行更左的值更小，不可能，向下移動 (i++)。
• 若當前值 > target → 該列更下的值更大，不可能，向左移動 (j--)。

每步排除一行或一列，最多 m+n 步。

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int i = 0, j = matrix[0].size() - 1;
    while (i < matrix.size() && j >= 0) {
        if (matrix[i][j] == target) return true;
        else if (matrix[i][j] < target) ++i;
        else --j;
    }
    return false;
}

比較與選擇

本題矩陣整體有序，二分查找更優。但右上角掃描是更通用的技巧，適用於「行遞增、列遞增」的矩陣（如 LeetCode 240），值得掌握。

總結

搜索有序二維矩陣，核心在於利用有序性質將二維問題降維。二分查找直接映射到一維索引最簡潔高效；右上角掃描則是處理「部分有序」矩陣的利器。面試中建議先給出二分法，再延伸討論右上角法的適用範圍。