查找：顺序查找的实现以及相关优化

1.算法思想

顺序查找，又叫“线性查找”，通常用于线性表。
适用于顺序表、链表，表中元素有序无序都OK。

可在0索引处存“哨兵”，从尾部向头部挨个查找优点:循环时无需判断下标是否越界。

代码实现（哨兵）：

typedef struct{//查找表的数据结构(顺序表)
    ElemType xelem;//动态数组基址
    int TableLen;//表的长度
}sSTable;

//顺序查找
int Search_Seq(sSTable ST,ElemType key){
    sT.elem[0]=key;//“哨兵”
    int i;
    for( i=ST.TableLen;ST.elem[i] !=key;--i);//从后往前找
    return i;//查找成功，则返回元素下标;查找失败，则返回C
}
1
2
3
4
5
6
7
8
9
10
11
12

2.查找效率分析

ASL = ${\sum }_{i=1}^n$PiCj

1.查找成功的情况

ASL成功 = （n+1)/2 . (n代表查找的是第n个元素)
时间复杂度为O(N）

2.查找失败的情况

ASL失败为n+1，时间复杂度也为O(N）

3.顺序查找的优化1（有序表）

优点：可以提高ASL失败的查找效率。

1.算法步骤

1. 将表中元素进行排序：使查找表中元素有序存放(递增/递减)。
2. 这样就只需要判断查找目标是否在元素的左右区间即可。
3. 共有N+1种查找失败的情况（即N+1个区间）
4. 计算这种优化下的查找失败的ASL(平均查找长度)为：N/2+N/(N+1);

2.用查找判定树分析ASL

• 一个成功结点（即圆形结点）的查找长度=自身所在层数。
• 一个失败结点（即方形结点）的查找长度=其父节点所在层数。
• 默认情况下，各种失败情况或成功情况都等概率发生。

3.顺序查找的优化2（被查概率不相等）

优点：可以提高ASL成功的查找效率。
ASL = ${\sum }_{i=1}^n$PiCj

1. 被查概率大的关键字放在靠前位置
2. 从而提高查找成功ASL的效率

但无论那种优化，算法的的时间复杂度都不会低于O(N)这个数量级。