Java查找算法——(四)分块查找(完整详解,附有代码+案例)
文章目录
- 分块查找
- 1.1普通分块查找
分块查找
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;// 调用方法,传递索引表、数组、numberint 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 b3return 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;}
}