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

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;
    }

    // 解法三 线性搜索 利用每一行/列 递增的性质 达到进阶要求 O(m+n) !
    bool Find(int target, vector<vector<int> > array) {

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

        bool ans = false;

        int up = 0, right = n-1;

        while(up<m && right>=0) // 从右上开始   答案是从左下开始 同理都可以
        { // 注意终止条件 就是碰到某面墙 到最下面 或最左侧
            if(array[up][right] == target)
            {
                return true;
            }

            if(array[up][right]>target)
            {
                right--;
            }
            else
            {
                up++;
            }
        }

    
        

        return ans;
        
    } 
};