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.

1.迭代

class Solution {public:    bool searchMatrix(vector
     
      
       >& matrix, int target) {        int m = matrix.size();        int n = m==0 ? 0:matrix[0].size();        int i=0,j=n-1;        while(i
       
        =0){            if(matrix[i][j] < target) i++;            else if(matrix[i][j] > target) j--;            else return true;        }        return false;    }};
       
      
     

 

2.递归

class Solution {public:    bool searchMatrix(vector
     
      
       >& matrix,int r,int c,int target){        if(c<0 || r >= matrix.size()){            return false;        }        if(matrix[r][c]>target){            return searchMatrix(matrix,r,c-1,target);        }else if(matrix[r][c]
       

>& matrix, int target) { int m = matrix.size(); if(m==0){ return false; } int n = matrix[0].size(); return searchMatrix(matrix,0,n-1,target); }};