大厂面试真题题解：搜索二维矩阵

写出一个高效的算法来搜索 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作比较，然后移动区间端点。
算法流程：

• 将数组matrixi下标转换为 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;
    }
}

更多题解参考：九章官网Solution