写出一个高效的算法来搜索 m × n 矩阵中的值。 这个矩阵具有以下特性：

• 每行中的整数从左到右是排序的。
• 每行的第一个数大于上一行的最后一个整数。

在线做题地址

样例 1:

输入: [[5]],2 输出: false          样例解释:  没有包含，返回 false 。 

样例 2:

输入:   [   [1, 3, 5, 7],   [10, 11, 16, 20],   [23, 30, 34, 50] ],3  输出: true          样例解释:  包含则返回 true 。 

解题思路：

题目提到，给定的数组已经排序，若是一个一维数组，直接一次二分查找即可。现在题目给了一个二维数组，那么处理一下数组的下标，仍然按照一维数组二分即可。

二分查找常用于查找有序数组中目标数 target 的位置，用 left 和 right 记录 target 所在的区间端点，每次将区间的中间位置值和 target 作比较，然后移动区间端点。

算法流程：

• 将数组 matrix[i][j]下标转换为 i*col + j， 问题即转换为一维数组二分查找问题
• 将区间赋值为整个数组区间（ left = 0, right = n*m – 1 ），取中间位置 mid
• 若 a[mid] < target，则将区间缩小到原区间的右区间(left = mid + 1)
• 若 a[mid] > target，则将区间缩小至原区间的左区间(right = mid)
• 若 a[mid] = target，返回 true
• 当 left >= right 时，若 a[right] = target 则返回 true, 否则返回 false

复杂度分析：

• 时间复杂度：O(log(nm))
• 即将二维数组看作一个 n*m 大小的一维数组，二分查找值。
• 空间复杂度：O(1)
• 查找不需要开辟新的空间，只需在原数组基础上进行查找即可

代码：

public class Solution {     /**      * @param matrix, a list of lists of integers      * @param target, an integer      * @return a boolean, indicate whether matrix contains target      */     public boolean searchMatrix(int[][] matrix, int target) {         int n = matrix.length;         int col = matrix[0].length;         int left = 0, right = n*col - 1;                  while(left < right){             int mid = (right + left) / 2;             if(matrix[mid/col][mid%col] == target){                 return true;             }             else if(matrix[mid/col][mid%col] > target){                 right = mid;             }             else{                 left = mid + 1;             }         }                  if(matrix[right/col][right%col] == target){             return true;         }                  return false;     } } 

大佬有話說 (0)