LeetCode-240 Search a 2D Matrix II

题目描述

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

题目大意

给定一个二维整数数组，数组中的行和列都是按照递增顺序排列，要求查找二维数组中是否存在一个给定的数字。

示例

E1

解题思路

对每行进行二分搜索，若在当前没有找到给定的数字，则将搜索范围的终止位置缩小为当前位置（因为当在当前行，搜索停止且未找到数字时，说明找到的位置一定大于或小于目标数字，若小于目标数字，则将位置加一，将二分搜索的终止位置重新赋值更新，因为每一行也是递增排列，因此在该位置之后的每一行的数字一定大于目标数字。经过该操作可以减少查询次数）。

复杂度分析

时间复杂度：O(log(N))

空间复杂度：O(1)

代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0 || matrix[0].size() == 0)
            return false;
        bottom = 0, top = matrix[0].size() - 1;
        
        for(int i = 0; i < matrix.size(); ++i) {
            // 对每一行进行二分查找
            bool f = binSearch(matrix[i], bottom, top, target);
            if(f)
                return true;
        }
        
        return false;
    }
    
    bool binSearch(vector<int>& arr, int sta, int end, int& target) {
        // 如果二分查找到最后，判断是否找到目标数字，并且将二分范围缩小
        if(sta >= end) {
            top = (end == arr.size() - 1 ? top : (arr[end] > target ? end : end + 1));
            return arr[end] == target;
        }
        else {
            int mid = (sta + end) / 2;
            bool f;
            // 若找到直接返回true
            if(arr[mid] == target) {
                return true;
            }
            // 否则，若中间位置小于目标数字，则返回后半部分位置
            else if(arr[mid] < target) {
                f = binSearch(arr, mid + 1, end, target);
                return f;
            }
            // 否则，若中间位置大于目标数字，则返回前半部分位置
            else {
                f = binSearch(arr, sta, mid, target);
                return f;
            }
        }
    }
    
private:
    int bottom, top; 
};