剑指Offer-二维数组查找

zmngc 2018-09-09 原文

/**
 * 题目描述 :
 *      在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
 *      每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，
 *      判断数组中是否含有该整数。
 * Created by guo.chen on 2018/9/8.
 */
public class Solution {

    /**
     * 先使用二分法定位 筛选掉不可能的区间，
     * 再使用二分法分行查询每一个一维数组
     * @param target 目标值
     * @param array 二维数组
     */
    public static boolean findTarget(int target, int [][] array) {
        if(array.length==0){
            return false;
        }
        int rows = array.length;
        int cols = array[0].length;
        if(target<array[0][0] || target>array[rows-1][cols-1]){
            return false;
        }
        //先确定在哪一行
        int middle = 0, low = 0, high = rows-1;
        while (high>low){
            middle = (low + high) / 2;
            if(array[middle][0] > target)
                high = middle - 1;
            else if(array[middle][0] < target)
                low = middle + 1;
            else
                return true;
        }

        for(int x=0;x<high;x++){
            while (array[x][cols-1]<target)
                x++;
            low = 0;
            high = cols -1;
            while (high>=low){
                middle = (low + high)/2;
                if(array[x][middle] > target)
                    high = middle - 1;
                else if(array[x][middle] < target)
                    low = middle + 1;
                else
                    return true;
            }
        }

        return false;
    }

    /**
     * 根据二维数组的有序性，
     * 从第一行开始比较最后一位数和目标值的大小，
     * 如果目标值小叫筛选掉这一列(列索引减一)
     * @param target 目标值
     * @param array 二维数组
     */
    public static String findTarget2(int target, int[][] array){
        if(array.length==0 || array[0].length == 0){
            return "-1";
        }
        int rows = array.length;
        int cols = array[0].length;
        if(target<array[0][0] || target>array[rows-1][cols-1]){
            return "-1";
        }
        int x = 0, y = cols - 1;
        while (x<rows && y>=0){
            if(array[x][y] == target)
                return "坐标是:["+x+" ]["+y+"]";
            else if(array[x][y] > target)
                y--;
            else
                x++;
        }
        return "-1";
    }

    public static void main(String[] args){
        int [][] array = {{16,26,36,46,56,66,76,86},
                                    {17,27,37,47,57,67,77,87},
                                    {18,28,38,48,58,68,78,88},
                                    {19,29,39,49,59,69,79,89}};

        boolean flag = findTarget(68,array);
        System.out.println(flag);
        int [][] array2 = {{}};
        String index = findTarget2(58,array2);
        System.out.println(index);
    }
}