当前位置：首页 > article >正文

2025年- H61-Lc169--74.搜索二维矩阵(二分查找）--Java版

article 2025/8/30 6:31:40

1.题目描述

在这里插入图片描述

2.思路

方法一：
定义其实坐标，右上角的元素（0，n-1）。进入while循环（注意边界条件，行数小于m，列数要＞=0）从右上角开始开始向左遍历（比当前元素target小的元素），向下遍历（比当前元素target大的元素），如果while循环结束都没找到，返回false。
方法二：二分查找
若将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，我们可以在该数组上二分找到目标元素。可以二分升序数组的下标，将其映射到原矩阵的行和列上。
row = mid / 列数，表示这是第几行；
col = mid % 列数，表示这是该行中的第几个元素。

在这里插入图片描述

3.代码实现

方法一：

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length;int n = matrix[0].length;int row = 0;int col = n - 1; // 从右上角开始while (row < m && col >= 0) {if (matrix[row][col] == target) {return true;} else if (matrix[row][col] > target) {col--; // 往左走} else {row++; // 往下走}}return false;}
}

方法二：

public class H74 {public boolean searchMatrix(int[][] matrix, int target) {//二维矩阵“虚拟成一维数组”进行二分查找//行数int m= matrix.length;//列数int n=matrix[0].length;//将矩阵展平成一维数组的容量int left=0;int right=m*n-1;while(left<=right){int mid=left+(right-left)/2;//防止整数溢出//将二维矩阵映射成一维数组//当前mid索引对应在矩阵的位置：当前元素的行数=mid/列数. // 将一维下标映射回二维坐标int row=mid/n;//当前元素的列数=mid/列数int col=mid%n;if(matrix[row][col]==target){return true;}else if(target>matrix[row][col]){left=mid+1;}else {right=mid-1;}}return false;}public static void main(String[] args){H74 ms=new H74();int[][] matrix={{1,3,5,7},{10,11,16,20},{23,30,34,60}};int target=11;Boolean res=ms.searchMatrix(matrix,target);System.out.print(res);}
}