線性表查找
順序查找
元素類型的定義和順序表的表示
image.png
查找算法
image.png
改進(jìn)
把待查的關(guān)鍵字key存入表頭（“哨兵”，“監(jiān)察哨”）匿值，可免去查找過程中每一步都需要檢測是否查找完畢赠制，加快速度。
示意圖
設(shè)置監(jiān)視哨的順序查找
當(dāng)ST.length較大時挟憔，此改進(jìn)的算法進(jìn)行一次查找的平均時間幾乎減少一半
時間效率分析
比較次數(shù)和key的位置有關(guān)
查找第i個元素钟些，需要比較n-i+1次；查找失敗绊谭，需要比較n+1次
時間復(fù)雜度O(n)
ASLs(n)=(n+1)/2
空間復(fù)雜度
O(n)= O(1)
image.png
優(yōu)缺點
