題目鏈接

/**

? ? ? ? 方案一:

? ? ? ? ? ? 每行都是遞增的,對每行進行二分,逐行查找;效率不高,每次搜索只能控制列無法兼顧到行,行被固定存在不必要的搜索

? ? ? ? 方案二:

? ? ? ? ? ? 從右上或左下頂點出發,以右上為例,向左迭代列減小,向下迭代行增大;效率更高避免重復搜索

*/

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;}}