上篇文中我们介绍了顺序查找和二分查找的相关概念及实现方式，本章小编带你了解下索引查找的知识点，首先我们先来看下基本概念。

索引查找的概念

索引查找是在索引表和主表(即线性表的索引存储结构)上进行的查找。

在实现索引查找算法前需要弄清楚以下三个术语。

1. 主表：即要查找的序列。
2. 查找表：一般我们会将主表分成几个块，每个块中的元素被称为是查找表。
3. 索引表：即索引项的集合。

索引查找又称为分块查找，是一种介于顺序查找和二分查找之间的一种查找方法。

索引查找的基本思想是：首先查找索引表，可用二分查找或顺序查找，然后在确定的块中进行顺序查找。

索引查找的实现

上面我们已经了解了相关的概念，下面我们再来看看具体怎么实现索引表，首先我们必须要创建主表，查找表及索引表。基本操作如下：

1. 分块：第Rk 块中所有关键字< Rk+1块中所有关键字，（k=1, 2, …, L-1）
2. 建立索引项：关键字项：记载该块中最大关键字值；指针项： 记载该块第一个记录在表中位置。
3. 所有索引项组成索引表。

其中分块是为了将主表分成小块组成查找表，2,3步是建立索引表方便我们进行查找。如下图所示：

算法实现的方法如下

首先根据待查找关键字K在索引表当中定位块。定位的方法有如下几个步骤

1. 只要key>索引块i的最大关键值，则i++，定位下一个索引项；
2. 直到定位到索引块，或者把索引项都定位完也没有比key关键字大的索引项。
3. 如果定位到块，则在块内部进行顺序查找。

代码实现如下：

int IndexSequelSearch(IndexType ls[], DataType s[], int m, KeyType key){  /*索引表为ls[0]-ls[m-1]，顺序表为s*/  i=0;  while(i<m && key>ls [i ].key)     i++; /*块间查找*/  if(i==m)    return -1; /*查找失败*/  else{ /*在块内顺序查找*/  	j=ls[ i ].Link;  while(Key!=s[j].key && j<ls[ i+1 ].Link)    j++;  if(key = = s[j].key)    return j; /*查找成功*/  else     return -1; /*查找失败*/ } }

上述代码中ls表示的是索引表就是分块后的表，s表示主顺序表

第4行确定key值在哪个索引表中

第8行取该索引表中的第一个数据

第10行在索引表中查找与key值相等的值。

本篇文章就介绍到这里，下一篇我们讲解下哈希的查找法