牛客网-二维数组的查找

//解决思路:
//如数组样式如下:
// 1 2 3 4
// 2 3 4 5
// 3 4 5 6
//正常查找的过程,本质就是排除的过程,如果双循环查找,本质是一次排除一个,效率过低
//根据题面要求,我们可以采取从右上角(或左下角)进行比较(想想为什么?),这样可以做到一次排除一行或者一列

public class Solution {
    public boolean Find(int target, int [][] array) {
         for (int[] ints : array) {
            for (int anInt : ints) {
                if(anInt==target)
                    return true;
            }
        }

        return false;
    }
}

        if(array==null)
            return false;

        int i = 0,//i：指向每一行最小的值
            j=array[0].length-1;//j：指向每一行最大的值

        while (i < array.length && j >=0 ){

            //此时array[i][j] 一定这一行最大的
            if(target < array[i][j]){
                j--;//如果比这一行的最大值小，指向这一行最大值的指针j就j-1,移动下一个元素

            //如果查找的数大于这个最大值，就说明肯定是在这一列，那么就i++就可以继续找这一列了
            }else if (target > array[i][j]){
                i++;

            //查找成功返回true
            }else{
                return true;
            }
        }

        return false;