题目
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
考察点和难度
- 考察知识点：数组
- 难度：4星（共5星）
分析
最简单的求解方式是遍历整个二维数组，可以查询到是否有目标值，但是时间复杂度为O(rows * cols)，面试官是不会满意的。
为了降低时间复杂度，需要运用该二维数组的特性，即横向和纵向的递增特性。
该二维数组中的任意一个点P，其左前区域都小于点P的值，其右后区域都大于点P的值，因此可以利用该特性在查询时缩小查询范围。
从最右上角的点P出发，如果点P的值等于目标值，则直接输出true；如果点P的值大于目标值，可以往左查找第一个小于等于目标值的点PL，此时点PL成为新的“右上角”，且点PL的右后部分区域的数值由于肯定大于目标值，因此可以被剔除出查询范围；如果点P的值小于目标值，可以往下查询第一个大于等于目标值的点PD，此时点PD成为新的“右上角”，且点PD的左前部分区域的数值由于肯定小于目标值，因此也可以被剔除出查询范围。得到新的“右上角”之后，重复该操作，就能遍历整个二维数组来查询目标值，且由于只在横向和纵向往左下角移动，剔除了无需查询的区域范围，因此时间复杂度为O(rows + cols)。
为什么从右上角出发开始查询？对于右上角的点P来说，其左边的数值都小于点P的值，其下面的数值都大于点P的数值，当给定目标值之后，如果目标值小于点P的数值，那么点P所在列就可以被剔除；如果目标值大于点P的数值，那么点P所在行就可以被剔除，这样就缩小了查询范围。
从左下角出发，往右上角查询也是可以的。
代码实现（java）
public boolean hasNumInArray(int[][] array, int rows, int cols, int num) {
// 检查输入参数
if (array == null) {
throw new NullPointerException();
}
if (rows < 1 || cols < 1) {
throw new IllegalArgumentException();
}
int rowSize = array.length;
if (rowSize != rows) {
throw new IllegalArgumentException();
}
int colSize = array[0].length;
if (colSize != cols) {
throw new IllegalArgumentException();
}
// 从右上角数字开始，往左下角找目标数字，理论上时间复杂度为O(rows+cols)
int i = 0, j = cols - 1;
while ((i <= (rows - 1)) && (j >= 0)) {
// 判断当前右上角的值是否为目标值
if (array[i][j] == num) {
return true;
} else if (array[i][j] > num) {
// 当前右上角的值比目标值大，则往左找新的“右上角”，且新的“右上角”的右后部分区域由于肯定大于目标值，因此可被剔除
while ((j >= 0) && (array[i][j] > num)) {
j = j - 1;
}
} else {
// 当前右上角的值比目标值小，则往下找新的“右上角”，且新的“右上角”的左前部分区域由于肯定小于目标值，因此可被剔除
while ((i <= (rows - 1) && (array[i][j]) < num)) {
i = i + 1;
}
}
}
return false;
}
