题目描述

编写一个高效的算法来搜索 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。

题解

左下角出发遍历法

根据本文所描述的特征, 每一行从左到右递增, 每一列从上到下递增, 所以可以根据贪婪思想决定每一步怎么走, 即:

当matrix[i][j]>target, 则直接删除改行数组, i--, 因为只能往上走才能找到更小的数
当matrix[i][j]<target, 则直接删除该列数组, j++, 因为只能往右走才能找到更大的数
若相等, 直接返回true

越界说明没找到, 返回false

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = matrix.length - 1;
        int j = 0;
        while (i >= 0 && j <= matrix[0].length - 1) {
            if (matrix[i][j] > target) i--;
            else if (matrix[i][j] < target) j++;
            else return true;
        }

        return false;
    }
}

二分查找(较慢)

因为矩阵已经排过序, 所以可采用二分查找的方法.

思路是遍历每一行的数组进行查找, 每当遍历到新的一行, 如果该行第一个元素都比目标值大, 那么直接返回false, 因为这已经是目前还没有遍历的数中最小的了.

如果该行数组最右的元素都比目标值小, 则直接开始遍历下一行, 因为这已经是这一行最大的数了, 没有查找的必要.

public boolean searchMatrix2(int[][] matrix, int target) {
        if (matrix.length==0||matrix[0].length==0)
            return false;
        for (int i =0; i<matrix.length;i++){
            if (matrix[i][0]>target)
                return false;
            if (matrix[i][matrix[0].length-1]<target)
                continue;

            int col = binarySearch1(matrix[i], target);
            if (col!=-1)
                return true;
        }

        return false;
    }

    private int binarySearch1(int[] matrix, int target) {

        int i = 0;
        int j = matrix.length-1;
        while (i<=j){
            int mid = (i+j)/2;
            if (matrix[mid]<target) i = mid+1;
            else if (matrix[mid]>target) j = mid-1;
            else return mid;
        }
        return -1;
    }