LeetCode 74 搜索二維矩陣：兩次二分查找定位行再列

題目描述

給定 m x n 矩陣，每行遞增，下一行首元素大於上行尾元素。判斷目標值是否存在。

範例：

matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3 → true

解題思路：兩階段二分查找

利用矩陣行首元素遞增性質：

1. 第一次二分：在所有行首元素中查找目標值所在行（最後一個 ≤ target 的行）
2. 第二次二分：在該行中查找目標值

時間複雜度：O(log m + log n) = O(log mn)，空間複雜度：O(1)。

C++ 參考實現

class Solution {
public:
    bool searchMatrix(vector>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        if (matrix[0][0] > target) return false;
        
        int r = matrix.size(), c = matrix[0].size();
        
        // 第一階段：查找目標行
        int low = 0, high = r - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (matrix[mid][0] == target) return true;
            else if (matrix[mid][0] < target) low = mid + 1;
            else high = mid - 1;
        }
        int row = low - 1;  // 最後一個行首 <= target 的行
        
        // 第二階段：在目標行中查找
        int left = 0, right = c - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[row][mid] == target) return true;
            else if (matrix[row][mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
};

完整測試代碼

#include 
#include 
using namespace std;

class Solution {
public:
    bool searchMatrix(vector>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        if (matrix[0][0] > target) return false;
        
        int r = matrix.size(), c = matrix[0].size();
        int low = 0, high = r - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (matrix[mid][0] == target) return true;
            else if (matrix[mid][0] < target) low = mid + 1;
            else high = mid - 1;
        }
        int row = low - 1;
        
        int left = 0, right = c - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[row][mid] == target) return true;
            else if (matrix[row][mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
};

int main() {
    Solution s;
    vector> nums1 = {{1,3,5,7}, {10,11,16,20}, {23,30,34,50}};
    bool t = s.searchMatrix(nums1, 11);
    cout << t << endl;  // 輸出 1 (true)
    return 0;
}

核心要點總結

• 兩階段策略：先定行、後定列，利用行首遞增性質
• 行索引計算：row = low - 1 取最後一個 ≤ target 的行首
• 對比單次二分：LeetCode 2812 文章的一維映射法更簡潔（O(log mn) 一次二分），本法邏輯更直觀易理解
• 邊界檢查：空矩陣、target 小於最小值早退出

兩次二分查找是解決「行列有序矩陣」的通用思路，當矩陣不滿足「全局一維有序」時（如 Matrix II），此法仍適用於行有序場景。