二维数组中的查找

题目描述

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

输入：
[[1， 2， 8， 9]，
[2， 4， 9， 12]，
[4， 7， 10， 13]，
[6， 8， 11， 15]]

给定target=7，返回true.

给定target=3，返回false.

数据范围：矩阵长宽满足0<n，m<500，矩阵中的值满足0<val<10^9

解法：二维数组的二分查找

思路：这道题是要在二维有序数组中查找元素，在一维有序数组中查找元素常用二分查找提高效率，因此想尝试拓展到二维。二分查找是通过不断缩小查询范围，每次查找使得搜索空间减半从而提高查找效率的。

在一维二分查找中，常采用数组首尾元素当做查找边界，但是这道题不可以这样做。比如如果（begin0，begin1）左上元素当做首节点，（end0， end1）右下当做尾节点，中间元素（mid0， mid1）和target比较大小，从而确定begin、end变量如何调整。但是在这道题中，按主对角线方向，对于任意元素，其上方和左方元素都比自身小，而其右方和下方元素都比自身大，所以比较大小后无法得到确定的调整方向。

但是如果以副对角线方向选择节点，任意一元素，其左方元素比自身小，下方元素比自身大；其上方元素比自身小，右方元素比自身大，因此选定左下或右上元素作为起点，可以通过比较target大小确定行列的收缩（扩张）范围。如果选择右上元素作为起点，如果target<node，列减小，应该向左侧移动；如果target>node，行增加，应该向下方移动。

代码

bool Find(int target， vector<vector<int>> array)
{
    bool res = false;
    int shape0 = array.size();
    if (shape0 == 0)
        return false;
    int shape1 = array[0].size();
    if( shape1 == 0)
        return false;

    int row = 0;
    int col = shape1-1;

    while(row<shape0 && col>-1)
    {
        if(target == array[row][col])
            res = true;
        if(target < array[row][col])
        {
            row--;
        }
        if(target > array[row][col])
        {
            col++;
        }
    }
    return res;
}