【算法学习】二维数组检索 search-a-2d-matrix（Java）

题目描述

请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征：
每一行的数字都从左到右排序
每一行的第一个数字都比上一行最后一个数字大
例如：
对于下面的矩阵：
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
要搜索的目标值为3，返回true；
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:

示例
输入 [[1,1]],0
输出 false

二、思路分析

有序列表检索可以用二分查找，二分查找参考链接

此题给出二维矩阵，每一行的数字都从左到右排序，每一行的第一个数字都比上一行最后一个数字大。通俗的说就是把一个有序数组折成二维矩阵而已。

• 思路1 空间允许的情况下，可以将二维数组转成一维数组。然后参考二分查找进行查找。
• 思路2 此题保证了从每行从左到右有序，并且第二行的第一个元素大于第一行所有元素。可以采用两次二分查找进行检索。

三、参考代码

/**
  * 
  * @param matrix int整型二维数组 
  * @param target int整型 
  * @return bool布尔型
  */
 public static boolean searchMatrix(int[][] matrix, int target) {
     // 查找列所在行
     if (matrix.length < 1 || matrix[0].length < 1) {
         return false;
     }
     int rowNum = 0;
     if (matrix.length > 1) {
         int left = 0, right = matrix.length - 1;
         int mid = 0;
         while (left <= right) {
             mid = left + (right - left) / 2;
             if (matrix[mid][0] == target) return true;
             if (matrix[mid][0] < target) left = mid + 1;
             if (matrix[mid][0] > target) right = mid - 1;
         }
         rowNum = mid;
     }
     // 行查找
     int left = 0, right = matrix[rowNum].length - 1;
     int mid;
     while (left <= right) {
         System.out.println(left + "  " + right);
         mid = left + (right - left) / 2;
         if (matrix[rowNum][mid] == target) return true;
         if (matrix[rowNum][mid] < target) left = mid + 1;
         if (matrix[rowNum][mid] > target) right = mid - 1;
     }
     return false;
 }

通过以下网站测试：

牛客网测试连接