分块查找

索引表 | 22 | 44 | 74 |
数组 | 22 12 13 9 8 | 33 42 44 38 24 | 48 60 58 74 47 |

算法步骤

1. 通过索引表线性查找确定在数组的哪一“块”
2. 通过数组里所在“块”的线性查找确定是否存在、在哪个位置

算法代码

Keytype  k; // 关键字
int blocks; // 整个索引表的长度
int last; // 整个数组的长度 last = blocks * L
index ix LIST  F ;
int L ;
Int   index_search(  k,  last, blocks, ix,  F,L  )
{
	int  i, j ; // i是索引表坐标，j是数组每块的坐标
	i = 0; // 第一位索引表
	while (( ix[i] < k) 	&&   (i < blocks) )  i++  ;
		// 当前查找值小于目标值 且  查找的坐标在索引表范围内
	if ( i < blocks ) { // i在范围内则说明上一行代码有查找到，不在范围内则没查找到
		j = i*L; // 每块长度为L，要在第i块内查找，数组内的坐标j为i×L
		while (( k != F[j].key ) && (j <= (i+1)*L-1 ) && (j < last))
			// 当前查找值目标值不同 且  坐标j在范围内   且 j在整个数组范围内（防止查找最后一“块”时越界）
			j = j + 1; // 查找块内的下一个查找元素
		if ( k == F[ j ].key )  return j ; // 若查找到则返回下标
		/* 	执行这条语句，有可能是：
			1. 上一个while的第一个条件不满足（即查找成功！）
			2. 第二/三个条件不满足（即越界≈无目标值，查找失败
		*/
	}
	return –1 ; // 查找失败
}