【查找算法系列】分块查找
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 + "}";
}
}