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

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param array int整型vector<vector<>> 
     * @return bool布尔型
     */
     
    bool Find(int target, vector<vector<int> >& array) {
        // write code here
        // for(int i=0;i<array.size();++i){
        //     for(int j=0;j<array[0].size();++j){
        //         if(target==array[i][j]){
        //             return true;
        //         }
        //     }
        // }
        // return false;
    //数组在C++中存放地址连续，在牛客上操作了一下不连续
    // int *p;
    // p=&array[0][0];
    //     for(int i=0;i<array.size()*array[0].size();++i){
    //         cout<<*p<<endl;
    //         if(target==*p){
    //             return true;
    //         }
    //         p+=1;
    //     }
    //      return false;
    // }
    //二分查找把每一行看成一个递增的数组时间复杂度O(nlogn)
        for(int i=0;i<array.size();++i){
            int low=0;
            int high=array[0].size()-1;
            while(low<=high){
                int mid=(low+high)/2;
                if(array[i][mid]>target){
                    high=mid-1;
                }else if(array[i][mid]<target){
                    low=mid+1;
                }else{
                    return true;
                }
            }
        }
        return false;
    }

   
};

每一行用二分法O(nlogn)