# 74 - Search a 2D Matrix

解法一 - Binary Search

這提我們可以先用 binary search 找到 target 所在的 row，然後再找 column，不過也可以把整個 2D matrix 當成一個 1D matrix，只要找出 array idx 對應到 matrix row 跟 column 的正確 mapping 方式就好。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if(m == 0) return false;
        int n = matrix[0].size();
        if(n == 0) return false;

        int l = 0, r = m * n - 1;
        while( l + 1 < r ) {
            int mid = l + (r - l) / 2;
            int midVal = matrix[mid/n][mid%n];

            if(midVal == target) {
                return true;
            }
            else if(midVal < target) {
                l = mid;
            }
            else {
                r = mid;
            }
        }

        if(matrix[l/n][l%n] == target) { return true; }
        else if(matrix[r/n][r%n] == target) { return true; }

        return false;
    }
};

// We can view this matrix as a array with length m*n-1
// We can change the index of 1d array to 2d matrix by arr[idx] == matrix[idx/n][idx%n]

這樣做的效率頗高：

Runtime: 8 ms, faster than 93.68% of C++ online submissions for Search a 2D Matrix. Memory Usage: 9.7 MB, less than 100.00% of C++ online submissions for Search a 2D Matrix.