一、题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
二、思路分析
首先分析该数组的特点，在向下和向右方向上，数值会递增。以二维数组中任意位置元素为例，同行右侧元素皆大于该点，同列下侧元素皆大于该点，因此该点右下侧元素皆大于该点。
而右上侧和左下侧点都可能有大于该点的点，初步可认为，大于该值的点位于右侧和下侧。因此，我们可以根据该数组的特点进行逐行剔除，达到缩小范围，查找目标值的目的。
算法思路
首先确定初始点，由于剔除某行 / 列，需要与目标值对比。初始点大于目标值，需要往小侧移动；初始点小于目标值，需要往大侧移动。而四个顶点，只有左下角和右下角，进行横向和纵向移动能高效筛选和剔除行列。
选择右上角为初始点，执行下述操作 1）如果该点等于目标值，结束查找 2）如果该点小于目标值，往大侧移动，下移一行（列索引不变）3）如果该点大于目标值，往小侧移动，左移一列（行索引不变）重复上述过程，直到索引超过数组边界。如果符合 1，退出重复。这里，我们认为本题找到目标值即可，无需查找是否有其他位置的目标值。
根据上述思路，通过向左下移动，达到整行或者整列的剔除，实现比较快速的查找。可以把这个过程理解为剥洋葱，一层层剥开外层的非目标层，查找内部的目标值。
三、Java 实现
源程序：
package jz_offer;
public class problem03
{
/**
* - 查找二维数据 arr 中是否存在数值 num
* @param arr：二维数组
* num：目标值
* @return 在二维数组中是否找到了目标值怒骂，返回类型 boolean
*/
public static boolean findNum(int[][] arr,int num){
boolean flag=false; // 标志位，为 true 时表示找到目标值
int i=0;
int j=arr[0].length-1;
while(flag!=true&&i<arr.length&&j>=0){
if(arr[i][j]==num){
flag = true;
break;
}else if(arr[i][j]<num){
i++;
}else{
j–;
}
}
return flag;
}
public static void main(String[] args){
int[][] array={{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
boolean found=findNum(array,7);
System.out.println(“if the num 7 is in the array?”+found);
}
}