南宁做网站价格,优秀网站架构,上海市建设工程安全生产协会网站,ftp修改网站文章目录 分块查找1.1普通分块查找 分块查找
1.1普通分块查找
分块原则#xff1a;
块内无序#xff0c;块间有序:前一块中的最大数据#xff0c;小于后一块中所有的数据#xff0c;块与块之间不能有数据重复的交集。块的数量一般等于数字个数开根号
核心思路#xff… 文章目录 分块查找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;}
}
