数据结构学习小记6之查找1
平均查找长度：
对于含有n个记录的表，查找成功的平均查找长度（ASL）为：
n
ASL=∑ PiCi
i=1
其中Pi为第i个查找表中记录的概率，且∑ pi=1；
Ci为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行比较的关键字个数，随查找过程不同而不同。
由于查找的基本运算是关键字之间的比较操作，所以可用平均查找长度来衡量查找算法的性能
顺序查找
（1）过程为：从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，在查找成功；反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败。
（2）顺序查找方法既适用于线性表的顺序存储结构，又适用于线性表的链式存储结构
（3）实现算法：以顺序表作为存储结构
数据元素类型定义：
typedef struct
{
KeyType key;//关键字域
InfoType otherinfo;//其他S域
}ElemType;
typedef struct
{ElemType *R;//存储空间基地址
int length; //当前长度
}SSTable;
【算法描述】
int Search_Seq(SSTable ST, KeyType key)
{for(i=ST.length;i>=1;--i)
if(ST.R[i].key==key) return i; //从后往前找，找到了就返回位置的下标
return 0;//没有查找成功返回0
}
以上这个算法每一步都要检测整个表是否查找完毕，即每一步都要检测是否i>=1，改进这个程序的方法是增加监视哨先对ST.R[0]的关键字赋值key(key为徐璈查找的关键字，ST.R[0]这个位置不用于存储，因为数据从末尾开始遍历，到ST.R[1]结束，所以ST.R[0]可以用于存储“哨兵”）
添加“哨兵”后的实现算法：
int Search_Seq(SSTable ST, KeyType key)
{ST.R[0].key=key;
for(i=ST.length;ST.R[i]!=key;--i)
return i; //从后往前找，找到了就返回位置
}
【算法分析】
时间复杂度为O(n);
n
ASL=1/n∑i=(n+1)/2;
i=1
顺序查找的优点是：算法简单，对表结构无任何要求。
缺点：平均查找长度较大，查找效率较低，所以当n很大时，不宜采取顺序查找。
2.折半查找（二分查找）
折半查找是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序结构且表中元素按关键字有序排列。
查找过程为：从表的中间记录开始，如果给定值和中间记录的关键字相等，则查找成功；如果给定值大于或者小于中间记录开始，则在表中大于或小于中间记录的那一半中查找，这样重复操作，直到查找成功，或者在某一步中查找区间为空，则代表查找失败。
【算法描述】
用low和high来表示当前查找区间的下界和上界，mid为区间的中心位置。
int Search_Bin(SSTable ST, KeyType key)
{
low=1;high=ST.length;//查找区间的初值
while(low<=high)
//循环执行的条件是low<=high而不是low<high,因为当low=high时，查找区间还有最后一个结点，还要进一步比较
{
mid=(low+high)/2;
if(key==ST.R[mid].key) return mid;//此时中间位置的元素恰为待查的元素
else if(key<ST.R[mid].key) high=mid-1;//在前一个表中查找
else low=mid+1;
}
return 0;//表中不存在待查元素
}
【算法分析】
折半查找过程可用二叉树来表示，
h
ASL=（1/n）∑ j*2^(j-1)=(n+1)/nlog2(n+1)-1
j=1
当n较大时有以下近似结果：ASL=log2(n+1)-1;
折半查找的时间复杂度为O(log2n),比较次数较少，查找的效率高，但是对表的要求高，只能用于顺序存储的有序表。折半查找不适用于数据元素经常变动的线性表。
分块查找：又叫索引顺序查找，这是一种性能介于顺序查找和折半查找之间的一种查找方法，在此查找法中需要建立一个“索引表”，索引表中含有最大关键字和起始地址，便于查找，若线性表既要快速查找又要经常动态变化，则可采用分块查找。
