面试题3:二维数组中的查找

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

分析

此题最直观的做法就是逐行逐列搜索。但这种做法没有利用数组有序递增这个特性,时间复杂度是O(m*n)(假设数组为n行m列)。肯定是不符合要求的。

所以可以有两种方法:从右上角搜索和二分法。

从右上角查找时,如果右上角的元素和待查找元素相等,则返回true;否则如果它大于待查找元素,根据题目所述,则当前有效数组的最后一列肯定不含有该元素,令其失效;同理,如果右上角元素小于待查找元素,则当前有效数组的最上面一行也是无效的。由此我们不断缩小数组范围便可以确定是否含有该元素。

代码如下

bool find(const vector<vector<int> >& matrix,int x)
{
    if(matrix.size()==0)
        return false;
    size_t row=matrix.size();
    int i=0,j=matrix[0].size()-1;
    while(i<row && j>=0)
    {
        if(matrix[i][j]==x)
            return true;
        else if(matrix[i][j]<x)
            i++;
        else
            j--;
    }
    return false;
}
1
2
3
4
### 二分法类似一维数组的二分查找,只不过对其行和列都进行二分。这样可以将数组分为上下左右四部分,然后对这四部分分别进行查找即可。
### 代码如下
bool _find(const vector<vector<int> >& matrix,int startm,int startn,int endm,int endn,int x) { if(matrix.size()==0 || startm>endm || startn>endn) return false; int leftn=startn,leftm=startm,rightn=endn,rightm=endm; int midn,midm; while(leftn<=rightn && leftm<=rightm) { midn=leftn+(rightn-leftn)/2; midm=leftm+(rightm-leftm)/2; if(matrix[midn][midm]==x) return true; else if(matrix[midn][midm]>x) { if(matrix[midn][leftm]>x ||matrix[leftn][midm]>x) { rightn=midn-1; rightm=midm-1; } else if(_find(matrix,leftm,midn,midm,midn,x) || _find(matrix,midm,leftn,midm,midn,x)) return true; else return false; } else { int tmpm=midm,tmpn=midn; leftm=midm+1; leftn=midn; if(_find(matrix,midm+1,midn,rightm,rightn,x) || _find (matrix,leftm,midn+1,rightm,rightn,x) || _find(matrix,midm+1,midn+1,rightm,rightn,x)) return true; else return false; } } return false; } bool find(const vector<vector<int> >& matrix,int x) { if(matrix.size()==0) return false; return _find(matrix,0,0,matrix[0].size()-1,matrix.size()-1,x); }

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:[点我前往]()