Problem 3：二维数组中的查找

一、题目描述

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

二、思路分析

首先分析该数组的特点，在向下和向右方向上，数值会递增。以二维数组中任意位置元素为例，同行右侧元素皆大于该点，同列下侧元素皆大于该点，因此该点右下侧元素皆大于该点。

而右上侧和左下侧点都可能有大于该点的点，初步可认为，大于该值的点位于右侧和下侧。
因此，我们可以根据该数组的特点进行逐行剔除，达到缩小范围，查找目标值的目的。

算法思路

首先确定初始点，由于剔除某行/列，需要与目标值对比。初始点大于目标值，需要往小侧移动；初始点小于目标值，需要往大侧移动。而四个顶点，只有左下角和右下角，进行横向和纵向移动能高效筛选和剔除行列。

选择右上角为初始点，执行下述操作
1）如果该点等于目标值，结束查找
2）如果该点小于目标值，往大侧移动，下移一行（列索引不变）
3）如果该点大于目标值，往小侧移动，左移一列（行索引不变）
重复上述过程，直到索引超过数组边界。如果符合1，退出重复。这里，我们认为本题找到目标值即可，无需查找是否有其他位置的目标值。

根据上述思路，通过向左下移动，达到整行或者整列的剔除，实现比较快速的查找。可以把这个过程理解为剥洋葱，一层层剥开外层的非目标层，查找内部的目标值。

三、Java实现

源程序：

package jz_offer;

public class problem03
{
    /**
     * -查找二维数据arr中是否存在数值num
     * @param   arr：二维数组
     *            num：目标值
     * @return  在二维数组中是否找到了目标值num，返回类型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);
    }    
}