分块查找算法

分块的原则

1. 前一块的最大数据，小于后一窥啊中所有的数据（块内无序，块间有序）
2. 块数数量一般等于数字的个数开根号。比如：16个数字一般分为4块左右。

public class blockSearch {
    public static void main(String[] args) {
        int[] arr = {16, 5, 9, 12, 21, 18,
                     32, 23, 37, 26, 45, 34,
                     50, 48, 61, 52, 73, 66};//共18个元素
        //要把数据进行分块：18开根号，根号18=4.24，所以分4块左右
        //将数据进行分为3块
        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 = blockSearch(blockArr, arr, number);
        System.out.println(index);
    }

    public static int blockSearch(Block[] blockArr, int[] arr, int number) {
        //1.先确定要查找的块
        int blockIndex = getBlockIndex(blockArr, number);
        if (blockIndex == -1) {
            return -1;
        }
        //2.再在块中进行查找
        int startIndex = blockArr[blockIndex].getStartIndex();
        int endIndex = blockArr[blockIndex].getEndIndex();
        for (int i = startIndex; i <= endIndex; i++) {
            if (arr[i] == number) {
                return i;
            }
        }
        return -1;
    }

    //确定要查找的块在哪个块中
    public static int getBlockIndex(Block[] blockArr, int number) {
        //遍历数组，找到要查找的块,如果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(int max, int startIndex, int endIndex) {
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    public Block() {
    }

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

扩展（无规律的数据）

class Block {
    private int max;//最大值
    private int min;//最小值
    private int startIndex;//起始索引
    private int endIndex; //结束索引
}

可以先找出块的最大值和最小值，每块的范围不重复，则可以将块分开

例如：27 22 30 40 36 13 19 16 20 7 10 43 50 48

可以分成4块，每块分别为: 27 22 30 40 36 , 13 19 16 20 , 7 10 , 43 50 48