Java基本查找、二分查找、插值查找、分块查找

太过爱你忘了你带给我的痛 2024-04-07 12:53 161阅读 0赞

**目录**

1、基本查找方法

2、二分查找

3、插值查找

4、分块查找

--------------------

### 1、基本查找方法 ###

基本查找核心：从0索引开始挨个往后查找

需求：定义一个方法，利用基本查找，查询某个元素是否存在

代码如下

/**
     * @authorDesc
     * @author
     * @date 
     * @version 1.0.0
     * @description 基本查找
     * 核心：从0索引开始挨个往后查找
     * 需求：定义一个方法，利用基本查找，查询某个元素是否存在
     */
    
    public class BasicSearch {
        public static void main(String[] args) {
            int[] numArray = {1,2,3,4,5,6,4,4};
            int number = 4;
            System.out.println(search(numArray,number));
        }
        /**
         * @description
         * @author 
         * @date 
         * @param numArray 数组
         * @param number 要查找的数字
         * @retur {@link int} 返回元素下表
         */
        public static int search(int[]numArray,int number){
            for (int i = 0; i < numArray.length; i++) {
                if (numArray[i] == number){
                    return i;
                }
            }
            return -1;
        }

需求：定义一个方法，利用基本查找，查询某个元素是否存在，如果有重复的元素，把所有元素找出

/**
         * @description
         * @author 
         * @date 
         * @param numArray 数组
         * @param number 要查找的数字
         * @return {@link List} 返回元素下标集合
         */
        public static List search(int[]numArray,int number){
            List<Integer> listnum = new ArrayList<>();
            for (int i = 0; i < numArray.length; i++) {
                if (numArray[i] == number){
                    listnum.add(i);
                }
            }
            return listnum;
        }
    }

### 2、二分查找 ###

前提条件：数组中的数据必须是有序的

核心：每次排除一半的查找范围

代码如下

/**
     * @authorDesc
     * @author
     * @date
     * @version 1.0.0
     * @description 二分查找
     * 核心：每次排除一半的查找范围
     * 需求：定义一个方法利用二分查找，查询某个元素是否在数组中
     */
    
    public class BinarySearch {
        public static void main(String[] args) {
            int [] numArray = {1,2,3,4,5,6};
            int number = 3;
            System.out.println(search(numArray,number));
        }
        /**
         * @description
         * @author
         * @date
         * @param numArray 数组
         * @param number 查找的数字
         * @return {@link int} 返回在数组中的下标
         */
        public static int search(int [] numArray, int number){
            //定义两个变量记录要查找的范围 min数组第一个元素的索引，max 数组最后一个元素的索引
            int min = 0;
            int max = numArray.length - 1;
            //利用循环查找
            while (true){
                if (min > max){
                    return -1;
                }
                //找到min和max的中间值
                int mid = (min + max) / 2;
                // 用mid 指向的元素和要查找的元素进行比较
                if (numArray[mid] > number){
                    //要查找的数字在mid的左边
                    //min不变， max = mid - 1
                    max = mid - 1;
                }else if (numArray[mid] < number){
                    //要查找的数字在mid的右边
                    //max不变，min = mid + 1
                    min = mid + 1;
                }else {
                    //查找的元素和mid指向得到元素一样
                    return mid;
                }
            }
        }
    }

二分查找的优势：提高查找效率

二份查找条件：1、数据必须是有序的

2、如果数据是乱的，先排序再用二分法查找得到的索引没有意义，只能确定当前数字在数组中是否存在，因为排序后的数字位置发生了变化

**二分查找的过程**：min和max表示当前要查找的范围

mid是在min和max中间的数字

如果要查找的元素在mid左边，缩小范围时，min不变，max等于mid减1

如果要查找的元素在mid右边，缩小范围时，max不变，min等于mid减1

### 3、插值查找 ###

//插值查找
    int mid = min + (number - numArray[min]) /(numArray[max] - numArray[min]) * (max - min);

和二分查找相似，将中间值mid改为：

int mid = min + (number - numArray\[min\]) /(numArray\[max\] - numArray\[min\]) \* (max - min);

### 4、分块查找 ###

原则：1、前一块中的最大数据，小于后一块中的所有数据（块内无序，块间有序）

2、块数数量一般等于元素个数的开根号，比如16个数字一般分为4块

核心：先确定要查找的元素在哪一块，然后在挨个查找

代码如下

/**
     * @authorDesc 
     * @author 
     * @date 
     * @version 1.0.0
     * @description 使用分块查找数组中的元素
     */
    
    public class BlockSearch {
        public static void main(String[] args) {
    
           int[] numArray = {2,3,1,4,
                            8,6,7,5,
                            9,11,10,12,
                            15,14,13,16};
           //创建三个快的对象
           Block b1 = new Block(4,0,3);
           Block b2 = new Block(8,4,7);
           Block b3 = new Block(12,8,11);
           Block b4 = new Block(16,12,15);
    
           //定义数组用来管理三个快的对象
            Block [] blockArray = {b1,b2,b3,b4};
    
            //定义一个变量用来记录要找的元素
            int number = 5;
            //调用方法，传递索引表，数组，要查找的元素
            int index = getIndex(blockArray,numArray,number);
            System.out.println(index);
        }
    
        /**
         * @description 定义一个方法，用来确定number在哪一块中
         * @author
         * @date
         * @param blockArray 数组
         * @param number 要查找的元素
         * @return {@link int} 返回下标
         */
        public static int findBlock(Block[] blockArray,int number){
            //Block b1 = new Block(4,0,3);-----0
            //Block b2 = new Block(8,4,7);-----1
            //Block b3 = new Block(12,8,11);----2
            //Block b4 = new Block(16,12,15);----3
    
            //从0索引开始遍历，如果bunber小于max，那么number就在这一块中
            for (int i = 0; i < blockArray.length; i++) {
                if (number <= blockArray[i].getMax()){
                    return i;
                }
            }
            return -1;
        }
        /**
         * @description
         * @author
         * @date
         * @param blocks 传递索引表，，
         * @param numArray 数组
         * @param number 要查找的元素
         * @return {@link int} 返回下标
         */
        public static int getIndex(Block [] blocks,int [] numArray,int number){
            //确定number实在那一块中
            int indexBlock = findBlock(blocks,number);
    
            if (indexBlock == -1){
                return -1;
            }
            //获取这一块的起始索引和结束索引
            //Block b1 = new Block(4,0,3);-----0
            //Block b2 = new Block(8,4,7);-----1
            //Block b3 = new Block(12,8,11);----2
            //Block b4 = new Block(16,12,15);----3
            int startIndex = blocks[indexBlock].getStartIndex();
            int endIndex = blocks[indexBlock].getEndIndex();
            //循环遍历
            for (int i = startIndex; i < endIndex; i++) {
                if (numArray [i] == number){
                    return i;
                }
            }
            return -1;
        }
    
    
    
        static class Block{
            private int max;//最大值
            private int startIndex;//起始索引
            private int endIndex;//结束索引
    
            public Block() {
            }
    
            public Block(int max, int startIndex, int endIndex) {
                this.max = max;
                this.startIndex = startIndex;
                this.endIndex = endIndex;
            }
    
            /**
             * 获取
             * @return max
             */
            public int getMax() {
                return max;
            }
    
            /**
             * 设置
             * @param max
             */
            public void setMax(int max) {
                this.max = max;
            }
    
            /**
             * 获取
             * @return startIndex
             */
            public int getStartIndex() {
                return startIndex;
            }
    
            /**
             * 设置
             * @param startIndex
             */
            public void setStartIndex(int startIndex) {
                this.startIndex = startIndex;
            }
    
            /**
             * 获取
             * @return endIndex
             */
            public int getEndIndex() {
                return endIndex;
            }
    
            /**
             * 设置
             * @param endIndex
             */
            public void setEndIndex(int endIndex) {
                this.endIndex = endIndex;
            }
    
        }
    }