剑指Offer-1-二维数组的查找

题目描述

  在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

Code

//解决思路n次二分查找，时间复杂度为O(nlogn)
class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int n=0;   
        for(int i=0;i<array.size();i++){
            if(binarySearch(array[i],0,array[i].size()-1,target)!=-1)
                return true;
        }
        return false;
    }
    //二分查找
    int binarySearch(vector<int> arr,int begin,int end,int target){
        int mid;
        while(begin<=end){
            mid=(begin+end)/2;
            if(arr[mid]==target)
                return mid;
            if(arr[mid]>target)
                end = mid-1;
            if(arr[mid]<target)
                begin = mid+1;
        }
        return -1;
    }
};