题解 | #二维数组中的查找#

class Solution {
public:

    // 看题意似乎是正方形 no  可能是矩形 而且可能有重复元素！
    /**
     * 二分搜索 基本函数
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int binary_search(vector<int>& nums, int target) {
        // write code here

        int n = nums.size();
        int l = 0, r = n-1;
        int ans = -1;
        while (l<=r) // 终止条件注意！
        {
            int m = l+0.5*(r-l); //  0.5*(r+l) 注意这两个取中值都可以 不要混淆就行！

            if(nums[m]>target)
            {
                r = m - 1;
            }
            else if(nums[m]<target)
            {
                l = m+1;
            
            }
            else // 一定得保留此支路！
            {
                ans = m;
                break;
            }
        
        }

        return ans>=0 ? ans : -1;
    }

    // 双二分查找 递归 ！
    bool double_binary(vector<vector<int> >& nums, int target, int xl, int yl, int xr, int yr) {
        // 搜索范围由 (xl, yl) (xr, yr) 分别为左上 和 右下圈出的矩形
        if(xl>xr || yl>yr) // 类比二分搜索的终止条件
            return false;
        
        int xm = 0.5*(xr+xl);
        int ym = 0.5*(yr+yl);

        if(nums[xm][ym]==target)
            return true;
        
        if(nums[xm][ym]>target) // 分块 但注意各块不再规则 而且分块方式有两种
        {
            if(double_binary(nums, target, xl, yl, xm-1, yr ))
                return true;
            if(double_binary(nums, target, xm, yl, xr, ym-1))
                return true;
        }
        else
        {
            if(double_binary(nums, target, xm+1, yl, xr, yr ))
                return true;
            if(double_binary(nums, target, xl, ym+1, xm, yr))
                return true;
        }
        
        return false; //别忘了
    }

    // 解法四 递归 二分搜索 利用每一行/列 递增的性质  O(logm logn) !
    bool Find(int target, vector<vector<int> > array) {

        int m = array.size(), n = array[0].size();

        bool ans  = double_binary(array, target, 0, 0, m-1, n-1);
        
        return ans;
    } 
};