題目鏈接

搜索二維矩陣

題目描述

注意點

• 每行中的整數(shù)從左到右按非嚴(yán)格遞增順序排列
• 每行的第一個整數(shù)大于前一行的最后一個整數(shù)
• 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;}
}

關(guān)鍵點

• 二分查找的思想
• 如果target介于某一行的最小值和最大值之間，且在該行沒有找到target，說明二維矩陣中肯定沒有target