顺序查找

算法思想

• 顺序查找又称线性查找，它对顺序表和链表都是适用的。对于顺序表，可通过数组下标递增来顺序扫描每个元素；对于链表，可通过指针next来依次扫描每个元素。顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字有序的线性表的顺序查找。

顺序查找的实现

顺序查找的实现(带哨兵)

• 优点：无需判断是否越界，效率更高

查找效率分析

顺序查找的优化(对有序表)

• 若在查找之前就已经知道表是关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度。
• 假设表L是按关键字从小到大排列的，查找的顺序是从前往后，待查找元素的关键字为key,当查找到第，个元素时，发现第z.个元素对应的关键字小于key,但第1+1个元素对应的关键字大于key,这时就可返回查找失败的信息，因为第，个元素之后的元素的关键字均大于key,所以表中不存在关键字为key的元素
• 有序线性表的查找可以是顺序存储结构也可以是链式存储结构
  

用查找判定树分析ASL

顺序查找的优化(被查找的概率不相等)

总结