LeetCode:74. Search a 2D Matrix搜索二维矩阵(C语言)

快来打我* 2022-12-05 15:26 124阅读 0赞

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

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

示例 1:

输入:  
matrix = \[  
\[1, 3, 5, 7\],  
\[10, 11, 16, 20\],  
\[23, 30, 34, 50\]  
\]  
target = 3  
输出: true

示例 2:

输入:  
matrix = \[  
\[1, 3, 5, 7\],  
\[10, 11, 16, 20\],  
\[23, 30, 34, 50\]  
\]  
target = 13  
输出: false

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/search-a-2d-matrix  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){ 
        if (!matrixSize || !matrixColSize){ 
            return false; 
        }  
    
        int left = 0;                                  //最左上角
        int right = (*matrixColSize) * matrixSize - 1; //最右下角
        int mid = 0;
        int row= 0 ;
        int column = 0;;  
        
        while (left <= right) { 
            mid = left + ((right - left)/2);
    
            row = mid / *matrixColSize;  // 除法取整行(定位此行)
            column = mid % *matrixColSize;  // 取余得到列(定位此列)
    
            if (matrix[row][column] == target){ 
                return true;
            } 
            else if (matrix[row][column] > target){ 
                right = mid - 1;
            } 
            else{ 
                left = mid + 1;
            }
        }
        return false;
    }

**运行结果：**  
![在这里插入图片描述][20200911111816294.png_pic_center]  
**Notes：**  
二分查找

[20200911111816294.png_pic_center]: /images/20221123/6d976abf4b56455d8a07a56df29aa146.png