分块查找,也称为块搜索或索引-顺序搜索,是一种常见的查找算法,主要用于在已排序的数据块或块中快速定位目标元素。它结合了顺序查找和二分查找的优点,并使得在大规模数据集中进行查找更加高效。
分块查找的基本思想是将数据划分为多个块,并对每个块进行排序。
分块查找的优点是在执行查找时可以跳过一些不必要的块,从而提高查找效率。它适用于静态数据集(即不经常更新的数据集)以及对内存敏感的应用程序。然而,由于需要预处理数据集,因此在数据集经常变化的情况下,它的效率可能会降低。
分块查找适用于数据较多,但是数据不会发生变化的情况,如果需要一边添加一边查找,建议使用哈希查找
分块查找的过程:
需要把数据分成N多小块,块与块之间不能有数据重复的交集。
给每一块创建对象单独存储到数组当中
查找数据的时候,先在数组查,当前数据属于哪一块
再到这一块中顺序查找
需求:
定义一个方法利用分块查找,数据如下:{16, 5, 9, 12,21, 18, 32, 23, 37, 26, 45, 34, 50, 48, 61, 52, 73, 66}
要求:查询某个元素是否存在
示例:
package text.text02;
/*
分块查找:
当数据表中的数据元素很多时,可以采用分块查找。汲取了顺序查找和折半查找各自的优点,既有动态结构,又适于快速查找
分块查找适用于数据较多,但是数据不会发生变化的情况。
分块查找的过程:
1. 需要把数据分成N多小块,块与块之间不能有数据重复的交集。
2. 给每一块创建对象单独存储到数组当中
3. 查找数据的时候,先在数组查,当前数据属于哪一块
4. 再到这一块中顺序查找
*/
public class text10A {
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};
//定义两个要查询的数(一个能查到,一个查不到)
int number1 = 23;
int number2 = 49;
//创建块对象,将arr数组按照一定的规律分块(块内无序,块间有序)
Block block1 = new Block(21, 0, 5);
Block block2 = new Block(45, 6, 11);
Block block3 = new Block(73, 12, 17);
//定义数组,将块对象添加进数组
Block[] blocks = {block1, block2, block3};
System.out.println("==========基本查找/顺序查找==========");
//调用judgeIndex1方法,判断要查询的数在块对象中的索引 (judgeIndex1方法用的是基本查找)
int index1 = judgeIndex1(blocks, number1);
int index2 = judgeIndex1(blocks, number2);
//调用judgeNumber方法,根据judgeIndex1方法返回的索引判断要查询的数在该arr数组中是否存在
judgeNumber(arr, blocks, index1, number1); //23存在,该数在数组中的索引为:7
judgeNumber(arr, blocks, index2, number2); //49不存在
System.out.println("==========二分查找/折半查找==========");
// 调用judgeIndex2方法,判断要查询的数在块对象中的索引 (judgeIndex2方法用的是折半查找/二分查找)
int index3 = judgeIndex2(blocks, number1);
int index4 = judgeIndex2(blocks, number2);
//调用judgeNumber方法,根据judgeIndex2方法返回的索引判断要查询的数在该arr数组中是否存在
judgeNumber(arr, blocks, index1, number1); //23存在,该数在数组中的索引为:7
judgeNumber(arr, blocks, index2, number2); //49不存在
}
//创建方法,判断要查询的数在哪块对象中,即在块对象中的索引(基本查找/顺序查找)
public static int judgeIndex1(Block[] blocks, int number) {
//利用循环遍历块对象数组,查找要查询的数的索引
for (int i = 0; i < blocks.length; i++) {
//如果要查询的数小于该块对象中的最大值
if (number <= blocks[i].getMax()) {
//返回该块对象的索引
return i;
}
}
return -1;
}
//创建方法,判断要查询的数在哪块对象中,即在块对象中的索引(折半查找/二分查找)
public static int judgeIndex2(Block[] blocks, int number) {
//折半查找中的起始索引
int min = 0;
//折半查找中的结束索引
int max = blocks.length - 1;
//折半查找中的中间索引
int mid = (min + max) / 2;
//利用循环查找要查找的数在块对象数组中的索引
while (true) {
//如果起始索引小于结束索引,表明没找到
if (min < max) {
return -1;
}
//如果要查找的数大于块对象数组中间索引的最大值
if (number > blocks[mid].getMax()) {
min = mid + 1;
}
//如果要查找的数小于块对象数组中间索引-1的最小值
else if (number < blocks[mid - 1].getMax()) {
max = mid - 1;
}
//如果要查找的数大于块对象数组中间索引-1的最小值并且小于块对象数组中间索引的最大值
else if (number < blocks[mid].getMax() & number > blocks[mid - 1].getMax()) {
return mid;
}
}
}
//创建方法,判断要查找的数在judgeIndex块对象中已经确定的块对象区域中是否存在
public static void judgeNumber(int[] arr, Block[] blocks, int index, int number) { //index为blocks块对象数组中的索引
for (int i = blocks[index].getStartIndex(); i <= blocks[index].getEndIndex(); i++) {
if (arr[i] == number) {
System.out.println(number + "存在,该数在数组中的索引为:" + i);
return;
}
}
System.out.println(number + "不存在");
}
}
//创建块类
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;
}
public String toString() {
return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
}
}
基本查找/顺序查找:
二分查找/折半查找: