算法定义

分块查找，也叫索引顺序查找，算法实现除了需要查找表本身之外，还需要根据查找表建立一个索引表。

建立的索引表要求按照关键字进行升序排序，查找表要么整体有序，要么分块有序。

分块有序：指的是第二个子表中所有关键字都要大于第一个子表中的最大关键字，第三个子表的所有关键字都要大于第二个子表中的最大关键字，依次类推。

块（子表）中各关键字的具体顺序，根据各自可能会被查找到的概率而定。如果各关键字被查找到的概率是相等的，那么可以随机存放；否则可按照被查找概率进行降序排序，以提高算法运行效率。

算法原理

所有前期准备工作完成后，开始在此基础上进行分块查找。分块查找的过程分为两步进行：

1、确定要查找的关键字可能存在的具体块（子表）；
2、在具体的块中进行顺序查找。

方法描述

将n个数据元素”按块有序”划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须”按块有序”；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……。

例子： 在表中查找值为38的元素。
方法：首先建立索引表如下图，把38与22比，38>22，所以该元素不在第1块，因为第1块的元素的最大值是22，与48比，38<48，则在第2块，然后在第二块里进行顺序查找。

性能分析
分块查找的比较部分发生在两个步骤里，一个是关键字与索引表作比较，另一个是关键字逐个和块内元素作比较，所以查找效率为：

ASL = L_b + L_w

L_b ：对索引表查找的ASL.

L_b ​= log₂(s/n ​+ 1)​

L_w ：对块内查找的ASL。

L_w​ = s / 2​

其中，s为每块内部的记录个数，n/s即块的数目。
所以，分块查找的效率为，

ASL ≈ log₂(n/2 ​+ 1)​ + s/2​

分块查找的效率介于折半查找和顺序查找之间，但更加接近于折半查找。

优缺点

优点：插入和删除比较容易，无需进行大量的移动。
缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算。
适用情况：如果线性表既要快速查找又经常动态变化，则可采用分块查找。

算法实现

#include <stdio.h>
#include <stdlib.h>
struct index {  //定义块的结构
    int key;
    int start;
} newIndex[3];   //定义结构体数组
int search(int key, int a[]){
    int i, startValue;
    i = 0;
    while (i<3 && key>newIndex[i].key) { //确定在哪个块中，遍历每个块，确定key在哪个块中
        i++;
    }
    if (i>=3) {  //大于分得的块数，则返回0
        return -1;
    }
  ...

掌握本节内容