剑指offer_01_二维数组中的查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解题思路
该二维数组中的一个数，他左边的数都比他小，下边的数都比他大。因此，可以从右上角开始查找，根据target与数组中元素的关系来缩小查找区间，当前元素的查找区间为该元素左下角的所有元素。
假设数组为
array[4][4]={1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16};
target=14;
那么数组左上角元素为array[0][3]=4，查找过程如下图所示

1. 将array[0][3]与target比较，4小于14，则行标 r增加1
   
2. 将array[1][3]与target比较，8小于14，则行标 r再增加1
   
3. 将array[2][3]与target比较，12小于14，则行标 r继续增加1
   
4. 将array[3][3]与target比较，16大于14，则列标 c减小1
   
5. 将array[3][2]与target比较，15大于14，则行标 c继续减1
   
6. 将array[3][1]与target比较，14等于14，说明已在array中找到target，返回true
   
7. 如果从数组右上角查找到左下角都没有找到target，则说明数组中不存在要查找的target,返回false

Java代码实现如下

public static boolean Find(int target, int[][] array) {
    if (array == null)
        return false;
    // 判断输入是否为空，如果为空则直接返回false
    int row = array.length, cols = array[0].length;
    // 数组行数为row，列数为cols
    int r = 0, c = cols - 1;
    // c=cols-1,列标最大值为列数减1
    while (r <= row - 1 && c >= 0) {
        // 当满足行标小于行数减1 ，并且列标大于等于0的条件时，进行查找
        if (target == array[r][c])
        return true;
        // 如果该元素与target相等，返回true
        else if (target > array[r][c])
        r++;
        // 如果target大于数组元素，则将其和该元素下方元素进行比较
        else
        c--;
        // 如果target小于数组元素，则将其和该元素左边元素进行比较
    }
    return false;
    // 如果没有找到，返回false
    }

测试结果如下：