本文共 1561 字，大约阅读时间需要 5 分钟。

题目

解析

暴力

class Solution {
   public:    bool searchMatrix(vector
   
    
     >& matrix, int target) {
           int m = matrix.size(), n = matrix[0].size();        for(int i=0;i
    
   

剪枝

初始左下角指针（row = matrix.size()-1,col=0）：

• 如果等于target，返回true；
• 如果小于target，col+=1(因为每行从左到右，从小到大)；
• 如果大于target，row-=1(因为每列从下到上，从大到小)；

简而言之，每个指针，所在列上面的会比它小，下面会比它大；所在行左边比它小，右边比它大；

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

二分法

class Solution {
   public:    bool searchMatrix(vector
   
    
     >& matrix, int target) {
           for(int i = 0; i < matrix.size(); ++i)        {
               if(binarySearch(matrix, i, target))                return true;        }        return false;    }    bool binarySearch(vector
     
      
       >& matrix, int i, int target)    {
           int left = 0, right = matrix[0].size()-1;        while(left <= right)        {
               int mid = left + (right - left)/2;            if(target > matrix[i][mid]) left = mid+1;            else    if(target < matrix[i][mid])    right = mid-1;              else    return true;         }        return false;    }};/*作者：zrita链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/c-xian-xing-cha-zhao-er-fen-z-by-zrita/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/