分块查找

1.1普通分块查找

分块原则：

• 块内无序，块间有序:前一块中的最大数据，小于后一块中所有的数据，块与块之间不能有数据重复的交集。
• 块的数量一般等于数字个数开根号

核心思路：先确定要查找的元素在哪一块，然后再该块内查找。

汲取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找

分块查找适用于数据较多，但是数据不会发生变化的情况，如果需要一边添加一边查找，建议使用哈希查找

每块中的最大值有序，如下：

public class BlockSearchTest {
    public static void main(String[] args) {
  /*分块查找
 核心思想：块内无序，块间有序
 实现步骤：
 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 = 5;
        // 调用方法，传递索引表、数组、number
        int index = getIndex(blockArr, arr, number);
        //打印number的索引
        System.out.println(index);

    }
    //定义方法：用分块查找原理 查询num的索引
  public static int getIndex(Block[] blockArr,int[] arr,int num){
        // 1.确定num在哪一块中,indexBlack:表示第几块的索引
        int indexBlack = indexFindBlack(blockArr, num);
        if (indexBlack == -1){
            // 表示numme没有在数组中
            return -1;
        }
        //2. 获取这一块块的起始索引和结束索引
      int startIndex = blockArr[indexBlack].getStartIndex();
        int endIndex = blockArr[indexBlack].getEndIndex();
        //3. 遍历
        for (int i = startIndex; i < endIndex; i++) {
            if (arr[i] ==num){
                return i;
            }
        }
        return -1;
    }
  
 // 定义一个方法，确定要找的元素num在哪一块中
public static int indexFindBlack(Block[] blockArr,int num){
   // 从0索引开始遍历blockArr，如果num小于max,就表示num在这一块中
        for (int i = 0; i < blockArr.length; i++) {
            if (num <= blockArr[i].getMax()){
                // 此处i表示第几块,即 块的对象b1 b2 b3
                return i;
            }
        }
        return -1;
    }
}
//创建数组的分块的类
class Block{//块
    private int max;//块中最大值
    private int startIndex;//块内起始索引
    private int endIndex;//块内结束索引
    public Block() {}
    public Block(int max, int starIndex, 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 setStarIndex(int startIndex) {
        this.startIndex = startIndex;
    }
    public int getEndIndex() {return endIndex;}
    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }
}