二分查找----2.搜索二维矩阵

题目链接

/**

        方案一:

            每行都是递增的,对每行进行二分,逐行查找;效率不高,每次搜索只能控制列无法兼顾到行,行被固定存在不必要的搜索

        方案二:

            从右上或左下顶点出发,以右上为例,向左迭代列减小,向下迭代行增大;效率更高避免重复搜索

*/

class Solution {/**方案一: 每行都是递增的,对每行进行二分,逐行查找;效率不高,每次搜索只能控制列无法兼顾到行,行被固定存在不必要的搜索方案二:从右上或左下顶点出发,以右上为例,向左迭代列减小,向下迭代行增大;效率更高避免重复搜索*/public boolean searchMatrix(int[][] matrix, int target) {int row = matrix.length;int col = matrix[0].length;/** 对每行进行二分for(int i = 0; i < row; i++) {int left = 0;int right = col - 1;//单次二分while(left <= right) {int mid = (left + right) >>> 1;if(matrix[i][mid] == target) {return true;} else if(matrix[i][mid] < target) { //淘汰左半区left = mid + 1;} else { //淘汰右半区right = mid - 1;}}}return false;*///从右上开始,向左/下搜索int x = 0, y = col - 1;while(y >= 0 && x < row) {if(matrix[x][y] == target) {return true;} else if(matrix[x][y] < target) { //偏小,向下搜索x++;} else { //偏大,向左搜索y--;}}return false;}}