本文共 3076 字，大约阅读时间需要 10 分钟。

一、分块查找

分块查找又称为索引查找，他是一种性能介于顺序查找和二分查找之间的查找方法。它要求按如下的索引方式来存储线性表：将R[0…n-1]均分为b块，前b-1块中的记录个数为s=n/b，最后一块即第b块的记录小于等于s；每块中的关键字（元素）不一定有序，但前一块中的最大关键字必须小于后一块的最小关键字，即要求表示“分块有序”的；抽取各块中的最大关键字及其起始位置构成一个索引表IDX[0…b-1]，即IDX[i]（0<=i<=b）中存放着第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表示一个递增有序表。

分块查找的基本思想是：首先查找索引表，因为索引表是有序表，故可以采用二分查找或顺序查找，以确定待查记录在那一块；然后在已确定的块中进行顺序查找（因为内无序，只能用顺序查找）。如果在块中找到该记录则查询成功，否则查找失败。

示例：有如下数字构成的序列：A={8, 14, 6, 9, 10. 22, 34, 18, 19, 31, 40, 38, 54, 66, 46}，请求分块查找算法查询给定的数值10是否存在，并输出结果。

要利用分块查找算法查询给定的数值10，首先将原序列分成三块{ [8, 14, 6, 9, 10], [22, 34, 18, 19,31], [40, 38, 54, 66, 46] },对应的索引表为{

{14，0}，{34，5}，{66，10}}，而索引表里包含索引项（如{34,5}），每项内容包含每块最大关键字和索引块的开始位置。

public class SSTable {       private int data[];    private int length;    public int searchIndex(IndexTable it, int m, SSTable st, int n, int k) {           int low = 0, high = m -1, mid, i;        int b = n/m;        while (low <= high) {               mid=(low + high) / 2;            if (it.elem[mid].key >= k) {                   high = mid - 1;            } else {                   low = mid + 1;            }        }        if (low < m) {               i = it.elem[low].start;            while (i <= it.elem[low].start + b -1 && st.data[i] != k) {                   i++;            }            if (i <= it.elem[low].start + b -1){                   return i;            } else {                   return -1;            }        }        return -1;    }    public void  createSSTable(int[] a){           this.data = new int[a.length];        for (int i = 0; i < a.length; i++) {               this.data[i] = a[i];            this.length++;        }    }    /* 索引表结点 */    public class IndexItem {           public  int key;        public  int start;    }    /* 索引表 */     public class IndexTable{           public  IndexItem[] elem;        public int length = 0;        public void createIndexTable(int[][] b){               this.elem = new IndexItem[b.length];            int i;            for (i = 0; i < b.length; i++){                   elem[i] = new IndexItem();                elem[i].key = b[i][0];                elem[i].start = b[i][1];                this.length++;            }        }    }    public static void main(String[] args) {           int[] a = {   8, 14, 6, 9, 10, 22, 34, 18, 19, 31, 40, 38, 54, 66, 46};        int[][] b = {   {   14, 0},{   34, 5},{   66, 10}};        SSTable st = new SSTable();        IndexTable it = st.new IndexTable();        st.createSSTable(a);        it.createIndexTable(b);        int x = st.searchIndex(it, b.length, st, a.length, 10);        if (x < 0) {               System.out.println("要查找的元素不存在");        } else {               System.out.println("查找成功，该元素在表中的位置为：" + (x + 1));        }    }}

算法分析：由于分块查找实际上是两次查找过程，因此整个查找过程的平均查找长度是两次查找的平均查找长度之和。若以二分查找来确定块，则分块查找成功时的平均查找长度为:ASLblk=ASLbn+ASLsq=1og2(h+1)-1+(s+1)/2≈1og2(n/s+1)+s/2,若以顺序查找确定块,则分块查找成功时的平均查找长度为: ASL’blk=ASLbn+ASLsq=(b+1)/2=s^2 + 2s+ 。显然,当s=根号n时,ASL’blk取极小值,即采用顺序查找确定块时,应将各块中的记录数选定为√n。如表中有记录1000条,则应把它分为100个块,每个块中包含100个记录。用分块查找平均要做100次比较，而顺序查找平均需要做5000次比较个奇找只需要14次比较。由此可见，分块查找算法的效率介于顺序查找和二分查找之间。