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

目录

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;
        }
 
    }
}