Java – 算法 – 分块查找

简介

分块查找算法，指的是把一个数组中分成若干个区间块，每个区间块都有一定的取值范围，把这些取值范围组合成一个索引数组，通过对比查找值与区间值，我们可以知道，这个值在那个区间内，我们只需要通过直接遍历那个区间里的成员就可以了。

分块查找原理

分块原则：

1.前一块中的最大数据，小于后一块中所有的数据

2.块数数量一般等于数组的个数开根号，比如：16个成员，那么应该是分4组左右

当我们需要查找时，我们选判断，这个值在那个块中可能出现，比如 30 ,我们能过查找索引表发现，第三个成员的 max 值是 40,那么值30，有可能就存在于这一组中，我们单独拎出来对这个组进行遍历就可以。

分块查找实现

/*
            分块查找
            核心思想：
                块内无序，块间有序
            实现步骤：
                1.创建数组blockArr存放每一个块对象的信息
                2.先查找blockArr确定要查找的数据属于哪一块
                3.再单独遍历这一块数据即可
        */
        int[] arr = {16, 5, 9, 12,21, 18,
                     32, 23, 37, 26, 45, 34,
                     50, 48, 61, 52, 73, 66};

        //创建三个块的对象
        Block b1 = new Block(21,0,5);
        Block b2 = new Block(45,6,11);
        Block b3 = new Block(73,12,17);

        //定义数组用来管理三个块的对象（索引表）
        Block[] blockArr = {b1,b2,b3};

        //定义一个变量用来记录要查找的元素
        int number = 37;

        //调用方法，传递索引表，数组，要查找的元素
        int index = getIndex(blockArr,arr,number);

        //打印一下
        System.out.println(index);

    }

    // 利用分块查找的原理，查询number的索引
    private static int getIndex(Block[] blockArr, int[] arr, int number) {
        // 1.确定number是在那一块当中
        int indexBlock = findIndexBlock(blockArr, number);

        if(indexBlock == -1){
            // 表示number不在数组当中
            return -1;
        }

        // 2.获取这一块的起始索引和结束索引   --- 30
        // Block b1 = new Block(21,0,5);   ----  0
        // Block b2 = new Block(45,6,11);  ----  1
        // Block b3 = new Block(73,12,17); ----  2
        // 取出这一分组中的起始索引和结束索引
        int startIndex = blockArr[indexBlock].getStartIndex();
        int endIndex = blockArr[indexBlock].getEndIndex();

        // 3.遍历
        for (int i = startIndex; i <= endIndex; i++) {
            if(arr[i] == number){
                return i;
            }
        }
        // 如果在这一组中都找不到，那说明其它组也是找不到的。
        return -1;
    }


    // 定义一个方法，用来确定number在哪一块当中
    public static int findIndexBlock(Block[] blockArr,int number){ //100


        //从0索引开始遍历blockArr，如果number小于max，那么就表示number是在这一块当中的
        for (int i = 0; i < blockArr.length; i++) {
            if(number <= blockArr[i].getMax()){
                return i;
            }
        }
        return -1;
    }
}

//  定义一个用于存储分据信息的类
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;
    }

    public int getMax() {
        return max;
    }

    public void setMax(int max) {
        this.max = max;
    }

    public int getStartIndex() {
        return startIndex;
    }

    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    public int getEndIndex() {
        return endIndex;
    }

    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }

    public String toString() {
        return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
    }
}

分块查找（无规律分组）

上面的分块查找可以分成多个块，每个块最大值都比后一个块中所有值都小，但如果大小值无规律，可以通过增加一个字段记录分块的最小值，最大值，来判断这一块中的值区间，通过查找该块的值区间大小，再进行遍历该区间中的成员即可。