[算法学习]二维数组的查找

算法

问题描述： 二维数组中的查找。在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样一个二维数组和一个整数，判断数组中是否包含该整数。
例如：
{
{1,2,3,4}
{2,4,6,7}
{4,5,7,8}
{6,7,8,9}
}

解法与分析： 可以使用二分法来查找。

  1. 从四个角中找一个起点，向列走是递增&向行走是递减，或者，向列走是递减&向行走是递增。符合这个条件的只有左下角和右上角。
  2. 以左下角为例，定义两个指针，一个向上走（减），一个向右走（增）。
  3. 如何走？判断当前两个指针所指向二维数组中的值比搜索值大还是小，比搜索值大的话，向上走，比搜索值小的话，向右走。直到两个指针都停止不能走为止。

参考代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 查找。我们从二维数组左下角找起会很快。(以下计算过程画个二维数组图，然后一行一行代码看会很容易理解的)
 * @param nums 二维数组
 * @param target 目标整数
 * @param column 取小列
 * @param row 取最大行
 * @return
 */
public static boolean findNum(int[][] nums,int target,int column,int row)
{
    if(nums==null)
    {// 防止 null异常
        return false;
    }
    while (column>0&&row>0)
    {
        int current=nums[row-1][column-1]; //当前值

        if(current>target)
        {// 当前值太大，缩行(向上面一行走,因为上面一行值会小一点)
            --row;
        }
        else if(current<target)
        {// 当前值太小，缩列(向右边一列走,因为右边一列值会大一点)
            ++column;
        }
        else
        {// 找到值
            return true;
        }
    }

    return false;
}