题目：

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.

代码：

class Solution {public:    bool searchMatrix(vector
     
      
       >& matrix, int target) {            if (matrix.size()==0) return false;            const int ROW = matrix.size();            const int COL = matrix[0].size();            // search the target row            int begin = 0;            int end = ROW-1;            while ( begin<=end )            {                int mid = (begin+end)/2;                int lower = matrix[mid][0];                int upper = matrix[mid][COL-1];                if ( target>=lower && target<=upper )                {                    return Solution::binarySearch(matrix[mid], target);                }                if ( target
       
        upper )                {                    begin = mid+1;                    continue;                }            }            return false;    }    static bool binarySearch(vector
        
         & row, int target)    {            int begin = 0;            int end = row.size()-1;            while ( begin<=end )            {                int mid = (begin+end)/2;                if ( row[mid]==target ) return true;                if ( row[mid]>target )                {                    end = mid-1;                }                else                {                    begin = mid+1;                }            }            return false;    }};
        
       
      
     

tips：

1. 首先二分查找可能所在的行

2. 确定某一行之后，再二分查找所在的列

完毕。

======================================

另一种思路：把大的二维矩阵当成一个一维数组看，只需要执行一次二分查找就OK了。

class Solution {public:    bool searchMatrix(vector
     
      
       >& matrix, int target) {            if (matrix.size()==0) return false;            const int ROW = matrix.size();            const int COL = matrix[0].size();            int begin = 0;            int end = ROW*COL-1;            while ( begin<=end ){                int mid = (begin+end)/2;                int val = matrix[mid/COL][mid%COL];                if ( val==target ) return true;                if ( val>target ){                    end = mid-1;                }                else{                    begin = mid+1;                }            }            return false;    }};
      
     

tips：

注意这条语句“int val = matrix[mid/COL][mid%COL]”。

一开始写成了"int val = matrix[mid/ROW][mid%COL]" 掉入了这个思维陷阱，因为每行有多少列应该是基础长度单元，所以不论是取商还是余数，分母上都应该是COL。

============================================

第二次过这道题，沿用一般的思路，先找可能在哪一行；再去行里面找。

class Solution {public:    bool searchMatrix(vector
     
      
       >& matrix, int target) {            // search for row            int row = -1;            int begin = 0;            int end = matrix.size()-1;            while ( begin<=end )            {                int mid = (begin+end)/2;                if ( matrix[mid][0]<=target && matrix[mid][matrix[mid].size()-1]>=target )                {                    row = mid;                    break;                }                else if ( matrix[mid][0]>target )                {                    end = mid-1;                }                else                {                    begin = mid+1;                }            }            if ( row==-1 ) return false;            // search in the row            begin = 0;            end = matrix[row].size()-1;            while ( begin<=end )            {                int mid = (begin+end)/2;                if ( matrix[row][mid]==target ) return true;                if ( matrix[row][mid]>target )                {                    end = mid-1;                }                else                {                    begin = mid+1;                }            }            return false;    }};