搜索二维矩阵

题目链接

搜索二维矩阵

题目描述

注意点

• 每行中的整数从左到右按非严格递增顺序排列
• 每行的第一个整数大于前一行的最后一个整数
• 1 <= matrix.length, matrix[0].length <= 100

解答思路

• 先二分查找找到target所处的行，找到行后再二分查找找到target所处的列即可

代码

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int row = matrix.length;int col = matrix[0].length;int top = 0, bottom = row - 1;while (top <= bottom) {int rowMid = (top + bottom) / 2;if (matrix[rowMid][0] > target) {bottom = rowMid - 1;} else if (matrix[rowMid][col - 1] < target) {top = rowMid + 1;} else {int left = 0, right = col - 1;while (left <= right) {int colMid = (left + right) / 2;if (matrix[rowMid][colMid] == target) {return true;}if (matrix[rowMid][colMid] > target) {right = colMid - 1;} else {left = colMid + 1;}}return false;}}return false;}
}

关键点

• 二分查找的思想
• 如果target介于某一行的最小值和最大值之间，且在该行没有找到target，说明二维矩阵中肯定没有target