【前言】

今天是力扣打卡第八天！

时间过得好快呀，一转眼又是一年立冬，铁汁们记的保暖哦。

原题：搜索二维矩阵

题目描述：

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

【注意】：也就是说，整个二维矩阵都是升序的。

示例1： 

  

   

    

     

    
    

     

      输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
     
    
   

    

     

    
    

     

      输出：true
     
    
  
 

 示例2：

  

   

    

     

    
    

     

      输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
     
    
   

    

     

    
    

     

      输出：false
     
    
  
 

题解： 

 【敲黑板】：其实这道题目的重点就在于：一维索引和二维索引间的互换

代码执行：

  

   

    

     

    
    

     

      bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
     
    
   

    

     

    
    

     
    //考虑特殊情况
     
    
   

    

     

    
    

     
    if(matrix == NULL || matrixSize == 0){
     
    
   

    

     

    
    

     
        return false;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    int row = matrixSize;//行数，这里需要注意一下
     
    
   

    

     

    
    

     
    int col = *matrixColSize;//列数
     
    
   

    

     

    
    

     
    //将二维索引化解成一维索引
     
    
   

    

     

    
    

     
    int left = 0;
     
    
   

    

     

    
    

     
    int right = row * col - 1;
     
    
   

    

     

    
    

     
    int mid = 0;
     
    
   

    

     

    
    

     
    int element = 0;
     
    
   

    

     

    
    

     
    while(left <= right){
     
    
   

    

     

    
    

     

              mid = left + (right - left) / 2;
     
    
   

    

     

    
    

     

              element = matrix[mid / col][mid % col];//将一维索引转化成二维索引，实际上使用的还是二维索引
     
    
   

    

     

    
    

     
        if(element > target){
     
    
   

    

     

    
    

     

                  right = mid - 1;
     
    
   

    

     

    
    

     

              }else if(element < target){
     
    
   

    

     

    
    

     

                  left = mid + 1;
     
    
   

    

     

    
    

     

              }else{
     
    
   

    

     

    
    

     
            return true;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return false;
     
    
   

    

     

    
    

     

      }
     
    
  
 

复杂度分析 ：

时间复杂度：O(logM*N), M和N分别是矩阵的行数和列数

空间复杂度：O(1)

结语：

今天是力扣打卡第8天！

坚持住哦，定个小目标，先不间断打满100天！！

送你一朵小红花啦！！！

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/121194866