LeetCode 74. Search a 2D Matrix [Medium] [C++] 解題筆記

這題給定一個 m x n 的陣列，此陣列每列皆是遞增排序好的，而且每列的最後一個數字一定小於下一列的第一個數字，題目要求在此陣列中搜尋特定數字是否存在。

EX:

    Input:

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

Ans: 3

想法:

        首先注意到這個陣列的每列都是排序好的，在每列之中搜索可以使用 binary search，

而每列之間的大小也是有序的(下一列的數都會大於上一列的數)，

因此我們可以使用兩次 binary search，第一次先在每列的最後一個數字之間搜索 target 會出現在哪一列，

找到之後再在該列使用一次 binary seacrh 搜尋 target。

另外還有一種方法，因為列與列之間是有序的，因此我們可以將整個陣列看成是一個排序好的一維陣列，

以上面範例為例，可以轉成一維陣列: [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 50]，然後在這個陣列上使用

binary search 找 target 即可。將二維陣列轉換為一維陣列可以採用轉換 index 的方式，

不需要真的額外宣告一個一維陣列。

Complexity: O(log(m*n)) time, O(1) space.

完整程式碼:

解法一 ( 2-pass binary search):

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

解法二 (one-pass binary search, index transform)

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