74. Search a 2D Matrix

解題思路

先找 row 再找 column 的 binary search 版本

明明題目本身很簡單，卻卡在某些 edge case 上面好久.....

程式碼

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