力扣面试150题--搜索二维矩阵

Day 82

题目描述

思路

此题其实就是二分搜索的变形，
首先将确定要查询的数位于哪一行，由于二维数组是有序的，就比较每行的第一个元素和最后一个元素，这里直接相等就返回。
最后，锁定到某一行后，就采取二分查找，找到就返回true 没找到就到终止条件，跳出循环返回false。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {//先确定在哪一个行int row=0;if(matrix[0].length==1){while(row<matrix.length){if(target==matrix[row][0]){return true;}row++;}return false;}while(true){if(target>=matrix[row][0]&&target<=matrix[row][matrix[row].length-1]){break;}row++;if(row>=matrix.length){return false;}}int beg=0;int end=matrix[row].length-1;int mid;while(beg<end){if(target==matrix[row][beg]||target==matrix[row][end]){return true;}mid=(beg+end)/2;if(target==matrix[row][mid]){return true;}else if(target<matrix[row][mid]){beg=beg;end=mid-1;}else{beg=mid+1;end=end;}}return false;}
}