Leetcode 74: search a 2D matrix //Leetcode 240: search a 2D matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

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

Given target = 3, return true.


 对于有序的数列的查找，首先想到的是binary search，

Solut1: 2D binary search to 1D binary search
时间复杂度为log(n * m)
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        //sanity check
        if (matrix.size() == 0 || matrix[0].size() == 0) return false;
        int left = 0;
        int right = matrix.size() * matrix[0].size() - 1;
        while (left <= right) {
            int mid =  left  + (right - left)/2;
            if (matrix[mid / matrix[0].size()][mid % matrix[0].size()] == target) {
                return true;
            } else if (matrix[mid / matrix[0].size()][mid % matrix[0].size()] < target) {
                left = mid + 1;  
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
};

Solu2: 由于行和列都是sorted的，可以先对列进行binary search,找到对应行， 然后对行进行bianry search，找到具体元素。 此题只能是先确定行再查找列，因为行与行之间都是递增的，但是列与列之间不一样。
时间复杂度是O（logm + logn）
显然solu2在时间效率上会更高。
 此题有个困惑点，为什么left <= right，跳出来是left > right， right 为什么为此时对应行呢？
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        //sanity check
        if (matrix.size() == 0 || matrix[0].size() == 0) return false;
        //get the exact row
        int left = 0;
        int right = matrix.size()-1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (matrix[mid][0] < target) {
                left = mid + 1;
            } else if (matrix[mid][0] > target) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        int row = right; ///?????
        if (row < 0) return false;
        left  = 0;
        right  = matrix[0].size() - 1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (matrix[row][mid] < target) {
                left = mid + 1;
            } else if (matrix[row][mid] > target) {
                right = mid -1;
            } else {
                return true;
            }
        }
        return false;
    }
};
对于上面的代码红色那行，一直不太理解，下面自己写了一个可以理解的代码， 确定行的时候，要注意，关注点在right，只有right > target的时候，left才是所在目标行，而如果以left为关注点，那么就会出错，因为left > target，根本不能确定target在left 还是在right.
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        //sanity check
        if (matrix.size() == 0 || matrix[0].size() == 0) return false;
        //get the exact row
        int left = 0;
        int right = matrix.size()-1;
        while (left < right - 1) {
            int mid = left + (right - left)/2;
            if (matrix[mid][0] < target) {
                left = mid;
            } else if (matrix[mid][0] > target) {
                right = mid;
            } else {
                return true;
            }
        }
        int row = 0;
        if (matrix[left][0] > target) return false;
        if (matrix[right][0] > target) row = left;
        else row = right;
        left  = 0;
        right  = matrix[0].size() - 1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (matrix[row][mid] < target) {
                left = mid + 1;
            } else if (matrix[row][mid] > target) {
                right = mid -1;
            } else {
                return true;
            }
        }
        return false;
    }
};


Search a 2D matrix II
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

For example,
Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.
Given target = 20, return false.

这个题目规律是整个matrix, 从左往右递增，从上往下递增， 要在这样的matrix里面高效地找到target，一开始的时候想像上面的题目那样使用binary search，但是发现需要四个方向的sorted array进行找，就是发现规律并不好找
后来看leetcode discussion上面，有三种方法处理这个题目： 

1. step-wise linear search: 即向上下左右走一步，这个是在一维array或者二维matrix里面search的最基本的方法： standard method。

对于这样的矩阵可以对角线进行查找，比如确定一个起点，eg: 右上角，如果target < current，往左走，如果target > current, 往下走，只可能往左或者往下走，这样的做法时间复杂度： O（m +n）

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        //sanity check
        if (matrix.size() == 0 || matrix[0].size() == 0) return false;
        //from right up corner
        int i = 0;
        int j = matrix[0].size()-1;
        while (i < matrix.size() && j >= 0) {
            if (target == matrix[i][j]) {
                return true;
            } else if (target < matrix[i][j]) {
                j--;
            } else {
                i++;
            }
        }
        return false;
    }
};

 2. Diagonal-based binary partition
对对角线进行binary search，找到target介于两个cell之间的那两个cell， 然后根据这两个cell对整个matrix进行partition， target必然位于右上的submatrix和左下的submatrix，然后再对这两个matrix进行diagonal-based binary partition最终会确定到只含有target的submatrix中。
这样做的时间复杂度是O（nlogn） ： 需要找到partition point : o(n）, 然后进行partition 去 2 submatrix =》 logn =》time complexity: O(nlogn)