遍历和二分法求解二维数组中查找问题

深碍√TFBOYSˉ_ 2022-06-17 07:29 160阅读 0赞

/**
     * Created by cuboo on 2017/4/20.
     * 问题：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
     * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
     */
    public class test {
        public static void main(String[] agrs){
            int[][] a;
            a = new int[8][8];
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                    a[i][j] = i+j;
                }
            }
            System.out.println(new test().binaryFind(5,a));
    
        }
    
        /**
         * 二维数据暴力遍历查找
         * @param target
         * @param array
         * @return
         */
        public boolean allFind(int target, int [][] array) {
            for(int i = 0;i < array.length;i++){
                for (int j = 0; j < array[i].length; j++) {
                     if (target == array[i][j]){
                         return true;
                     }
                }
            }
            return false;
    
        }
    
    
        /**
         * 二维数据二分法查找
         * @param target
         * @param array
         * @return
         */
        public boolean binaryFind(int target, int [][] array) {
    
            for(int i = 0;i < array.length;i++){
                if (binaryQuery(array[i],target)){
                     return true;
                }
            }
            return false;
        }
    
        /**
         * 二分法查找
         * @param target
         * @param array
         * @return
         */
        public  boolean binaryQuery(int[] array,int target){
            int length = array.length;
            int low = 0;
            int high = length - 1,middle = 0;
            while (low <= high){
                //判断奇数
                int tem = low + high;
                if (tem%2 == 0){
                    middle = tem/2;
                }else {
                    middle = tem/2 + 1;
                }
    
                if (target == array[middle]){
                    return true;
                }
                else if (target > array[middle]){
                    low = middle + 1;
                }else {
                    high = middle - 1;
                }
            }
            return false;
        }
    
    }