编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出:true
示例 2:
![](/i/l/?n=23&i=blog/3168894/202304/3168894-20230412171758764-2062377746.png)
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出:false
使用二分查找法,先在第一列上进行一次二分查找,找到最后一个小于等于目标值的行号,再在该行上进行二分查找:
1 bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){ 2 int left = 0, right = matrixSize - 1; 3 while (left <= right) { 4 int mid = left + (right - left) / 2; 5 if (matrix[mid][0] == target) return true; 6 else if (matrix[mid][0] > target) right = mid - 1; 7 else left = mid + 1; 8 } 9 int row = right; 10 if (row < 0) return false; 11 left = 0, right = matrixColSize[row] - 1; 12 while (left <= right) { 13 int mid = left + (right - left) / 2; 14 if (matrix[row][mid] == target) return true; 15 else if (matrix[row][mid] > target) right = mid - 1; 16 else left = mid + 1; 17 } 18 return false; 19 }
标签:right,target,int,矩阵,mid,力扣,74,left From: https://www.cnblogs.com/wlxdaydayup/p/17310535.html