原题
编写一个高效的算法来判断 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
解法
思想
先进行行的二分搜索，找出在哪一行之后再对列进行二分搜索。
代码
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0||matrix[0].length==0) return false;
int start = 0;
int end = matrix.length-1;
int width = matrix[0].length-1;
while(start<end){
int mid = (start+end)/2;
if(matrix[mid][width]==target) return true;
else if(matrix[mid][width]>target) end = mid;
else start = mid+1;
}
int row = start;
start = 0;
end = width;
while(start<end){
int mid = (start+end)/2;
if(matrix[row][mid]==target) return true;
else if(matrix[row][mid]>target) end = mid-1;
else start = mid+1;
}
if(matrix[row][start]!=target) return false;
return true;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode74-%e6%90%9c%e7%b4%a2%e4%ba%8c%e7%bb%b4%e7%9f%a9%e9%98%b5/
