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

分析

上面所描述的二维数组就是如下的数组：

1
2
3
4

1 2 8  9
2 4 9  12
4 7 10 13
6 8 11 15

如果我们想要在其中找到是否有7这个数，可以这样做。

  1. 首先，我们选择右上角的数字9，发现9大于7，并且9所在的这一列都是大于7的。那么这一列我们就不要了，也就是让column--即可。

  2. 然后，在选择右上角的数字8，和之前一样，8也是大于7，并且8所在的这一列都是大于7的，也让column--。

  3. 其次，还是选择右上角的2，这时2小于7，我们就把2所在的这一行去掉，即row++。

  4. 接下来，选择右上角的4，同样的道理，执行row++。

  5. 最后，选择右上角的7，发现相等，输出即可。

关键的步骤就是行与列的增加或减少，这里每次都选择右上角的数字。当然，选择左下角的数字道理是一样的，只不过，不能选择左上角和右下角的数字，因为这样看不出比7大或者小的数字在哪一行或哪一列。

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public class FindInPartiallySortedMatrix {
    public boolean Find(int target, int[][] array) {
        if (array.length == 0 || array[0].length == 0)
            return false;
        int rows = array.length - 1;
        int columns = array[0].length - 1;
        int row = 0;
        int column = columns;
        while (row <= rows && column >= 0) {
            if (array[row][column] < target) {
                row++;
            } else if (array[row][column] > target) {
                column--;
            } else {
                return true;
            }
        }
        return false;
    }
}

详解

第3行，对边界条件进行检查。第10行，如果我们选择的右上角的数字 array[row][column] 比目标数字target要小的话，就增加行数；如果我们选择的右上角的数字array[row][column]比目标数字target要大的话，就减小列数；否则就返回true，即找到这个数字。