🟡前言
21天挑战赛第三周，本文将讲述分块查找有关内容
活动地址：CSDN21天学习挑战赛
🟡概述
1️⃣定义
分块查找是折半查找（二分查找）和顺序查找的一种改进方法，分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序
2️⃣示意图
3️⃣核心思路
- 先确定查找元素在哪一块，然后在块内挨个查找（ 块内无序，块间有序 ）
- 前一块中最大数据小于后一块中所有数据
- 块的数量等于数字个数开根号
🟡查找思路
1.创建一个索引表，表中含有每一块的起始索引、终止索引和最大值，并生成一个标准的Javabean
2.查询要查找数字所在的块，并返回块的索引值
3.根据块的索引值查找该块的起始索引和终止索引
4.遍历块，查找数字
5.返回索引值，若无则返回-1
🟡代码实现
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}; //创建三个块对象 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 = 21; //调用方法求Index int Index = getIndex(blockArr,arr,number); //打印输出Index System.out.println(Index); } //查询number的索引值 private static int getIndex(Block[] blockArr, int[] arr, int number) { int Indexblock = findIndexBlock(blockArr,number); if(Indexblock == -1){ return -1; } //定义起始索引和终止索引 int startIndex = blockArr[Indexblock].getStartIndex(); int endIndex = blockArr[Indexblock].getEndIndex(); //查找元素对应索引 for (int i = startIndex; i <= endIndex; i++) { if(arr[i] == number){ return i; } } return -1; } //查询number索引值所在的块 private static int findIndexBlock(Block[] blockArr, int 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; } /** * 获取 * @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; } }
🟡结语
分块查找仅仅是一种二分查找和顺序查找的改进版本，分块需要人工分，也比较费时
