牛客网剑指offer01，二维数组中的查找

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

时间限制：1秒 空间限制：32768K

解析：

我们首先可以判断出这是一个有序数组，类似于

一开始我们用最笨的方法暴力遍历算法，两个循环嵌套，时间超时。

然后开始看着这个二维数组，在它的右上角是这一行的最大值，这一列的最小值，同理左下角是这一行的最小值，这一列的最大值。因此我们可以将元素定位到这个点，我们以右上角为例，当输入进来的元素大于这个值时，那么一定在这一行的 下面所以

行++，当这个值小于时一定在这个值的左边，列--。

继而c++代码如下

class Solution
{
    public bool Find(int target, int[][] array)// 
    {
       int col=array[0].Length-1;
        int row=0;
        while(row<=array.Length-1&&col>=0)
        {
            if(target>array[row][col])
                row++;
            else if(target==array[row][col])
                return true;
            else
              col--;
        }
        return false;
    }
}

第二种方法是二分法，我们可以把每一行都当做一个有序数组，二分法顾名思义，取半对折，排序完成后后找到中间的那个，与输入的值进行比较当大于输入值时，就留下大的那一半，继续进行对半直到找到相等的元素。

分析如下，输入的是array[] [],通过array.Length,求出行的长度，array[i].Length是在第i行下列的长度

代码如下：

public boolean Find(int target, int [][] array) {
    for(int i=0;i<array.length;i++){
            int low=0;
            int high=array[i].length-1;
            while(low<=high){
                int mid=(low+high)/2;
                if(target>array[i][mid])
                    low=mid+1;
                else if(target<array[i][mid])
                    high=mid-1;
                else
                    return true;
            }
        }
        return false;
    }