顺序查找

Sequential Search

过程 Procedure

. 从表的一端开始，依次将记录的关键字和给定值进行比较

. 如果相等，查找成功；若查找整个表后，没有匹配的记录，查找失败

顺序查找
Index	0	1	2	3	4	5	6	7	8	9
Data	12	10	21	7	9	18	32	4	61	5

伪代码 Pseudo Code

顺序查找

for(start to end of array)
{
    if (current_element equals to Key)  
    {
        print (current_index);
    }
}

性能分析 Analysis

. 优点：简单

. 缺点：ASL比较大，查找效率低

. 适用于线性表：顺序存储结构和链式存储结构

. 适用于数据量小的情况；当表特别大时，不适合顺序查找

. 时间复杂度 O(N)

. 最少查找次数1；最多查找次数n；平均查找次数|比较长度 ASL = (n + 1)/2

. 更多信息，请查看 Linear Sort