题目描述：

https://leetcode-cn.com/problems/search-a-2d-matrix-ii/submissions/

 

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:

现有矩阵 matrix 如下：

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。

给定 target = 20，返回 false。

题目分析：

1、第一次看题，觉得这道题直接两层for循环就搞定了，为啥还是中等难度呢？按照暴力解法，提交后确实能通过，但是用时很长；

2、暴力解法耗时长的原因是：程序占用了所有的搜索空间；

3、恰好最近在看分治思想，分治思想大概描述是：将复杂问题划分成多个简单子问题，然后将子问题的解合并成最终的解；

4、题目中行和列都是升序的，因此脑袋里蹦出了二分查找法，二分查找法就是运用了分治思想；

5、二分查找法：对于一个升序的线性结构，查找目标值时，可以先将目标值和线性结构中间值做比较，等于中间值，代表找到目标值；如果大于中间值，那么目标值可能在线性结构后半段；

     小于中间值， 那么目标值可能在线性结构前半段；重复执行前面的步骤，最终会得到最终的结果，而且搜索空间的占用率为50%左右；

6、这道题运用二分法时，还有一个优化点，由于行和列都是升序的，因此可以对宽度较小的行或列使用二分法；

Java代码&力扣运行结果---暴力法：

    public boolean searchMatrix1(int[][] matrix, int target) {
        if (matrix.length == 0) {
            return false;
        }
        int colSize = matrix[0].length;
        for (int[] ints : matrix) {
            for (int j = 0; j < colSize; j++) {
                if (ints[j] == target) {
                    return true;
                }
            }
        }
        return false;
    }

Java代码&力扣运行结果---二分法：

    public boolean searchMatrix2(int[][] matrix, int target) {
        if (matrix.length == 0) {
            return false;
        }
        for (int[] ints: matrix) {
            boolean result = binarySearch(0, ints.length - 1, ints, target);
            if (result) {
                return true;
            }
        }
        return false;
    }

    private boolean binarySearch(int start, int end, int[] nums, int target) {
        if (start <= end) {
            int middle = (start + end) >> 1;
            if (nums[middle] == target) {
                return true;
            } else if (nums[middle] > target) {
                return binarySearch(start, middle - 1, nums, target);
            } else {
                return binarySearch(middle + 1, end, nums, target);
            }
        }
        return false;
    }

 

Java代码&力扣运行结果---优化二分法：