题目

解答

这是一个二位矩阵搜索的题目，实际上就是一个二位数组，很简单，我们第一想到的方法肯定是暴力搜索法。

意思就是直接通过两层遍历来比较数组中是否有和目标数字相同的数字。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0) {
            return false;
        }
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[i].size(); j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }
};

暴力搜索法的时间复杂度是 $O(m*n)$ ，所以在数据量比较大的时候速度就会很慢的，我们来慢慢的优化这个算法。

题目给我们的条件是已经排好序的数据，所以我们在第一层循环中我们就可以确定目标的在哪个数组范围中，或者不存在。

由于是已经排序好的数组，如果目标数字大于数组的第一个数字，并且小于最后一个数字，说明目标数字就在这个数组中。
如果目标数字大于数组的最后一个数字，并且小于后面一个数组的第一个数字，说明目标数字不存在整个二位数组中。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0 || matrix[0].size()  == 0) {
            return false;
        }
        // 先判断target在什么范围里面
        vector<int> resArr;
        for (int i = 0; i < matrix.size(); i++) {
            vector<int> arr = matrix[i];
            if (target >= arr.front() && target <= arr.back()) {
                if (target == arr.front() || target == arr.back()) {
                    return true;
                } else {
                    resArr = arr;
                    break;
                }
            }
            if (i > 0) {
                if (arr.back() > target && arr.front() < target) {
                    return false;
                }
            }
        }
        
        for (int i = 0; i < resArr.size(); i++) {
            if (resArr[i] == target) {
                return true;
            }
        }
        return false;
    }
};

上面的算法我们通过分解成两步，把时间复杂度优化到了 $O(m+n)$ ，但是我们还是可以继续优化。

二分查找法是在有序数组中搜索比较常用的一种方法，二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

这里我们就可以对第二步使用二分查找法。

把数组分成两个部分，然后对比中间数和目标数的大小，如果目标数大于中间数，那我们就取右边子数组重复整个步骤；如果目标数小于中间数，那我们就取左边子数组重复整个步骤，直到数组无法分割。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0 || matrix[0].size()  == 0) {
            return false;
        }
        // 先判断target在什么范围里面
        vector<int> resArr;
        for (int i = 0; i < matrix.size(); i++) {
            vector<int> arr = matrix[i];
            if (target >= arr.front() && target <= arr.back()) {
                if (target == arr.front() || target == arr.back()) {
                    return true;
                } else {
                    resArr = arr;
                    break;
                }
                
            }
            if (i > 0) {
                if (arr.back() > target && arr.front() < target) {
                    return false;
                }
            }
        }
        
        // 使用二分法查找
        int left = 0;
        int right = resArr.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (target == resArr[left] || target == resArr[right]) {
                return true;
            }
            if (target < resArr[mid]) {
                // 左边
                right = mid - 1;
            } else if (target > resArr[mid]) {
                // 右边
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
};

二分查找法的时间复杂度为 $O(log_2n)$ ，所以以上算法的时间复杂度 $O(m + log_2n)$ ，还是最后的算法效率比较快一点。