/*折半查找
* a为线性表数组，n为数据元素总个数，key为要查找的关键值*/
int Binary_Search(int *a,int n,int key)
{
int low,high,mid;
low=1; //定义最低下标为纪录首位
high=n;
while(low<=high)
{
mid=(low+high)/2; //折半(取整)
if(keya[mid]) //若查找值比中值大
low=mid+1; //最低下标调整到中位下标大一位
else
return mid; //若相等则说明Mid即为查找到的位置，返回该位置地址
}
return 0;
}
(4)举例 假设有一有序表a={0,1,16,24,35,47,59,62,73,88,99},n=10,key=62。即除0下标外共10个数字，对它进行查找是否存在62这个数。
a.查找步骤： 第一步：.a[mid]=a[5]=47第二步：a[mid]=a[8]=73>key,则high=mid-1=7，此时，mid=(6+7)/2=6
第三步：a[mid]=a[6]=59
第四步：a[mid]=a[7]=key，查找成功。 b.时间复杂度分析 下面我们将这个数组的查找过程绘制成一棵二叉树如下：
由二叉树的性质4："具有n个结点的完全二叉树的深度为[log2^n]+1"，可知在最坏情况下查找到关键字或查找失败的次数为[log2^n]+1，最好情况为1次。相比于顺序查找的时间复杂度O(n)，折半算法的时间复杂度为O(logn)，显然效率高很多。
(2)算法实现
int Fibonacci_Search(int *a,int n,int key)
{
int low,high,mid,i,k;
low=1; //定义最低下标为纪录首位
high=n; //定义最高下标为纪录未位
k=0;
while(n>F[k]-1)
k++;
for(i=n;ia[mid]) //若查找纪录大于当前分隔纪录
{
low=mid+1; //最低下标调整到分隔下标mid+1处
k=k-2; //斐波那契数列下标减两位
}
else
{
if(mid<=n)
return mid; //若相等则说明mid即为查找的位置
else
return n; //若mid>n说明是补全数值，返回n
}
}
return 0;
}
二、线性索引查找 数据结构的最终目的就是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的纪录相关联的过程，一个索引由若干个索引项构成，每个索引项至少包含关键字和其对应的纪录在存储器中的位置等信息。索引技术是组织大型
数据库以及磁盘文件的一种重要技术。索引按照结构可以分为线性索引、树形索引和多级索引。所谓线性索引就是将索引项集合组织为线性结构，也成索引表。
1.稠密索引 稠密索引就是指在线性索引中，将数据集中的每个纪录对应一个索引项。对于稠密索引这个线索表而言，索引项一定是按照关键码有序的排列。
注意：索引表有序，即当我们要查找关键字时，可以用到折半、插值、斐波那契等有序查找算法，大大提高了效率。如下图，假如要查找的关键字是18的纪录，从右侧的数据表中查找，则只能顺序查找(需要6次)；从左侧索引表中查找，则只需两次折半查找就可以得到18对应的指针。可见，线性索引查找目的就是将数据从无序变为有序，进而使用有序查找算法提供效率。
2.分块索引 稠密索引因为索引项与数据集的纪录个数相同，所以空间代价很大。为了减少索引项的个数，我们可以数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项的个数。 (1)分块有序原则 分块有序，即把数据集的纪录分成可若干块，并且这些快需要满足两个条件： ★块内无序，即每一块内的纪录不要求有序; ★块间有序，如第二块所有纪录的关键字均要大于第一块中所有纪录的关键字......; (2)分块索引：对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引。其中，分块索引的索引项结构分三个数据项： ★最大关键码：用于存储对应块中的最大关键字，目的是使得在它之后的下一块的最小关键字也能比这一块最大的关键字要大; ★块长：存储了块中的纪录个数，以便于循环时使用; ★块首指针：用于指向块首数据元素的指针，便于开始对这一块中纪录进行遍历。
(3)分块索引表的查找过程 第一步：在分块索引表中查找要查的关键字所在的块; 第二步：根据块首指针找到相应的块，并在块中顺序查找关键码(块中纪录一般为无序)。 (4)分块索引的平均查找长度 设n个纪录的数据集被平均分成m块，每个块中有t条纪录，显然n=m*t，或者说m=n/t。 根据最好域最差的等概率原则： Lb为查找索引表的平均查找长度=(m+1)/2; Lw为查找某个纪录的平均查找长度=(t+1)/2; 可知，一次分块索引查找的平均查找长度为：ASLw=Lb+Lw=(m+1)/2+ (t+1)/2=(m+t)/2+1=(n/t+t)/2+1.即平均长度不仅仅取决于数据集的总记录数n，还和每一块的纪录个数t相关。 又n=m*t，ASLw=[(n/t+t)/2+1]>=[(n+t^2)/t]/2+1=[(m*t+t*t)/t]/2+1，假入m=t->t=√n，即分的块数