题目描述

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

/**
 * Created by ZengXihong 2019-05-26.
 */
public class Solution1 {
    /**
     * 寻找数字 target 是否在数组 array 中
     * 原理： 从数组的左下角开始寻找该数，
     * 如果该数大于目标，则目标数在该行之上，行数递减
     * 如果该数小于目标，则目标数在该数的右侧，列数递增
     * 否则当前数等于目标数
     * 如果从左下遍历到左上都不存在，即数组不包含目标数
     * @param array 数组
     * @param target 目标数字
     * @return
     */
        public boolean find(int [][] array,int target) {
            // 获取数组的行数，减 1 是因为获取数组某个值时取值从 0 开始
            int len = array.length-1;
            int i = 0;
            // 如果当前行数大于等于 0（即第一行） 并且 取的值的坐标列数小于第一行的元素个数，则继续比较
            while((len >= 0)&& (i < array[0].length)){
                //如果当前行的第 1 个数大于 目标数，则 目标数在此行之上，故行数 减 1
                if(array[len][i] > target){
                    len--;
                // 如果当前行数的第 i 个数小于目标数，则说明该数在i 的右侧 ，故 i 加 1
                }else if(array[len][i] < target){
                    i++;
                 //否则 这个数就为目标数
                }else{
                    return true;
                }
            }
            return false;
        }
}