搜索二维矩阵:整体二分

题目

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

你必须编写一个时间复杂度为 O(log(m * n)) 的解决方案。

链接

74. 搜索二维矩阵

思考

这道题目设计的很巧妙正好满足整体二分趋势,但是七七一开始的思路不是整体二分,而是受昨天的思路影响想到了普通的二分法

‍

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
//        定义行
        int m = matrix.length - 1;
//定义头尾部,定义一个h用来记录target可能在的行
        int top = 0;
        int bottom = m;
        int h = -1;
//头尾看完
        while (top <= bottom) {
//            防溢出写法
            int mid = top + (bottom - top) / 2;
            if (matrix[mid][0] == target) {
                return true;
//                第一个数小于目标数,目标数可能存在这一行,记录,同时查找下一行
            } else if (matrix[mid][0] < target) {
                h = mid;
                top = mid + 1;
            } else {
                bottom = mid - 1;
            }
        }
//目标数不在数组中,放回
        if (h == -1) return false;
        return findMatrix(matrix[h],0,matrix[h].length - 1,target);
    }

    private boolean findMatrix(int[] arr,int left,int right,int target) {
//        整体思路很简洁
        if (left > right) return false;
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return true;
        } else if (arr[mid] > target) {
            return findMatrix(arr,left,mid - 1,target);
        } else {
            return findMatrix(arr,mid + 1,right,target);
        }
    }
}

但是这个可不是最推荐的哦!接下来介绍二分另一版

class Solution {
    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;
            int row = mid / n;
            int col = mid % n;

            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

‍