74. Search a 2D Matrix ------ M

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.

Example 1:

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

Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

A:
----------------------3rd pass---------------------------------
This is a typical problem of binary search.
You may try to solve this problem by finding the row first and then the column. There is no need to do that. Because of the matrix's special features, the matrix can be considered as a sorted array. Your goal is to find one element in this sorted array by using binary search.

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();        
        int start = 0, end = m*n-1;// treat it as 1 D array
        while(start<=end){
            int mid = start+(end-start)/2;
            if(matrix[mid/n][mid%n] == target)
                return true;
            else if(matrix[mid/n][mid%n] > target){
                end = mid-1;
            }else{
                start = mid+1;
            }
        }
        return false;
    }
};

Mistakes:
1:    low <= high 给写成 low < high
2： 一开始没有用mid，而直接在下面写的，就TMD给忘了 / 2



-------------------------------2nd pass ---------search for row first, then search for col----------------

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int low = 0, high = m-1;
        while(low<high){
            if(low == high - 1){
                if(matrix[high][0] <=target)
                    low = high;
                break;
            }
            int mid = (low+high)/2;
            if(matrix[mid][0] > target){
                high = mid-1;
            }else{
                low = mid;
            }
        }
        int left = 0, right = n-1;
        while(left<right){ // search the row, indexed by low
            int mid = (left+right)/2;
            if(matrix[low][mid]==target)
                return true;
            if( matrix[low][mid] < target)
                left = mid+1;
            else
                right = mid-1;
        }
        return matrix[low][left]==target;
    }
}

Mistakes:

最后 确定了low和left后，忘了检测该位置是否为target了


--------------------------1st pass-----------------------
最简单的， 就是搜索第一列，找到行， 再搜索该行。

public class Search2DMatrix {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length, i =0;
        while(i+1<Math.min(m,n) && matrix[i][i]<target && matrix[i+1][i+1]<target)
            i++;
        int col = i,row = i;
        if( matrix[row][n-1] >= target ){ // if the last on row i < target, search this row
            while(col+1<n && matrix[row][col+1] <= target)
                col++;
        }else{ // else, linearly search the i_th row
            while(row+1<m && matrix[row+1][col] <= target)
                row++;
        }
        return matrix[row][col]==target;
    }
}

但是上面这个解法是错误的，  自己举个例子想想是为啥？？？？？？

Mistakes:
1: int  mid = (low + high) / 2 时， 当low =0., high =1 ----> mid =0  导致死循环
   解决方法，就是在while中加一个if 语句，来检测之。

2：当只有1行的时候， 就没有运行那个check  column的while语句了。


Learned: