day3(二维数组中的查找）

题目描述

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

 

提交链接：点击

 

解题思路：由于每一行，每一列都有序。于是对于所有列可以想到用二分查找，时间复杂度为logn，接着遍历所有行，时间复杂度为n，于是总的时间复杂度为O(nlogn)。

 

代码如下：

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int high,low,mid;
        for(int i=0;i<array.size();i++){ //遍历所有行
            high=array[i].size()-1;
            low=0;
            while(low<=high){   //对其中一行的所有列进行二分查找
                mid=(high+low)/2;
                if(array[i][mid]==target) return true;
                else if(array[i][mid]<target) low=mid+1;
                else high=mid-1;
            }
        }
        return false;
    }
};

附加：vector 遍历所有元素的3中方式

1.直接用下标

2.用迭代器

3.用copy函数

具体参照这篇博客