沈阳网站开发培训价格国内免费云服务器

给你一个满足下述两条属性的m*n整数矩阵

• 每行中的整数从左到右按非严格递增顺序排序
• 每行的第一个整数大于前一行的最后一个整数

给你一个整数target，如果target在矩阵中，返回true;否则返回false。

示例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

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10的4次 <= matrix[i][j], target <= 10的4次

解题思路：一次二分查找

 若将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，可以在该数组上二分找到目标元素。

bool searchMatrix(int** matrix,int matrixSize,int* matrixColSize,int target)
{int m = matrixSize,n=matrixColSize[0];int low = 0,high = m*n-1;while(low<high){int mid = (low + high )/ 2 +low;int x=matrix[mid/n][mid%n];if(x<target)  low = mid+1;else if(x>target)   high = mid-1;else  return true;}return false;
}