算法查找——分块查找
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;
}
}