当采用分块查找时,数据的组织方式为 ( )
分块查找是应用在数据变化频繁的排序场景,特点将数组分成多个块,块间必须有序,但是块内可以无序,并建立块的起始索引和块内最大值的辅助数组,查找时,先用二分搜索查找辅助数组确定在哪个块内,然后用顺序搜索遍历块内数组,最终完成查找。分快搜索充分利用了顺序搜索(支持数据变化)+二分搜索(查找效率高)两者的特点。
附上实现方式:
struct block {
int bindex;
int blen;
int bmax;
int* belements;
};
int Partition(int arr[], int start, int end) {
int pivot = arr[start];
int highvac = end;
int lowvac = start;
int direct = true; //true for right,false for left. start from left
while(lowvac < highvac) {
if(direct == true) {
if(arr[highvac] <pivot) {
arr[lowvac] = arr[highvac];
lowvac++;
direct = false;
} else {
highvac--;
}
} else {
if(arr[lowvac] > pivot) {
arr[highvac] = arr[lowvac];
highvac--;
direct = true;
} else {
lowvac++;
}
}
}
arr[highvac] = pivot;
return highvac;
}
int findXMaxValue(int arr[], int xmax, int start, int end) {
int p = 0;
int cmax = end - start +1;
int len = end;
if (xmax >= len+1) {
return p;
}
while(cmax != xmax) {
p = Partition(arr,start,end);
cmax = len-p+1;
if(cmax > xmax) {
start = p+1;
} else if ( cmax < xmax) {
end = p-1;
start = 0;
}
}
return p;
}
//find the max value
int findMaxValue(int arr[], int start, int end) {
int max = arr[start];
int len = end - start+1;
for(int i = 0; i < len; i++) {
if(max < arr[i]) {
max = arr[i];
}
}
return max;
}
int blockIndexSearch(block dest_arr[], int search, int array_size) {
//search the block index by binarysearch at first
int left = 0;
int right = array_size -1;
while(left <= right){
int amid = (right+left)/2;
int bmax = dest_arr[amid].bmax;
if (search > dest_arr[amid].bmax) {
left = amid +1;
} else {
//order search in block
int* belements = dest_arr[amid].belements;
int blen = dest_arr[amid].blen;
int bindex = dest_arr[amid].bindex;
for(int i = 0; i< blen; i++) {
if(search == belements[i]) {
return i+bindex;
} else {
i++;
}
}
right = amid-1;
}
}
return -1;
}
//generate blockIndex
block* blockIndex(int dest_arr[],int block_num, int array_size) {
static block* block_arr = new block[block_num];
int block_size = array_size/block_num;
int block_indexes[block_num];
int csize = array_size;
for( int i = 0; i < block_num-1 && csize > block_size; i++) {
int p = findXMaxValue(dest_arr,block_size, 0, csize-1);
csize = csize-block_size;
//cout << "Xmax position:" << p << endl;
block_indexes[i] = p;
}
block_indexes[block_num-1] = 0;
printArray(block_indexes,block_num);
//generate block-indexed array
for(int j = block_num -1; j >= 0; j--) {
int bindex = block_indexes[j];
int bend = array_size;
if (j != 0) {
bend = block_indexes[j-1];
}
int blen = bend - bindex;
int* belements = new int[blen];
for(int i = 0; i < blen; i++ ) {
belements[i] = dest_arr[bindex+i];
}
int bmax = findMaxValue(belements,0,blen-1);
struct block tblock = {bindex,blen,bmax, belements};
int index = block_num-1-j;
block_arr[index] = tblock;
}
return block_arr;
}
分块查找法要求将列表组织成以下索引顺序结构:
首先将列表分成若干个块(子表)。一般情况下,块的长度均匀,最后一块可以不满。
每块中元素任意排列,即块内无序,但块与块之间有序。
构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置,和每块中最大
关键字(或最小关键字)。索引表按关键字有序排列。