知識總覽：

順序查找：

算法思想：

從頭到腳挨個找或者從腳到頭挨個找適用于線性表(順序存儲和鏈式存儲都適用)，又叫線性查找

實現：

1個數組elem指向數組的起始位置，索引從0開始遍歷數組直到找到目標值返回索引下標，否則返回-1

順序查找-添加哨兵：

數組的第一個位置不存數據而是在查找的時候放目標值即哨兵，從索引1開始存放數據，然后從數組長度倒序查找比較目標值，如果找到目標值則返回索引下標，如果返回索引0證明沒找到目標值，添加哨兵是為了避免數組越界，發現到了哨兵的位置就不再查找

?

查找效率分析：?

評價一個查找算法要看平均查找長度即ASL，平均查找長度又分查找成功和查找失敗

假設找任何一個關鍵字的概率都是相同的，如果一共有n個關鍵字，假設找最后一個關鍵字則概率為1/n，如果找倒數第2個關鍵字，則需要對比2次，則找到的概率為2* 1/n，依次類推需要比較n次，則平均查找長度為(1+2+3+...+n)/n=(n+1)/2,查找失敗為查找所有的數據都沒有查找到，即比較了n+1次(有加1是因為哨兵還占了一個位置)，即查找成功和查找失敗的時間復雜度都為O(n)

順序查找的優化(對有序表)：

就是因為順序查找是挨個找，所以假如要查找的數組數據開始有順序的話就方便查找，視頻中說得有n+1種失敗的情況不知道從哪來的，可能是跟上邊查找效率分析有關，把每次失敗都加了區間范圍，然后根據n+1種失敗的情況再確定每次失敗的概率為1/n+1，第2段要比較2次失敗的概率為2*(1/n+1)。。。。。直到到如下數組中第n個數，因為n前后有2個范圍段所以加了2次n，最后得到ASL=n/2+(n+1)/n

用查找判定樹分析ASL：

方形節點為失敗節點，圓形節點為成功節點，?如果要找的關鍵字在圓形節點即成功節點中，要付出的查找長度(關鍵字的對比次數)=自身所在的層數，比如要找關鍵字19，要進行7,13,19三次對比，失敗節點的查找長度=父節點所在層數，假如關鍵字在13-19方形區間，直到確認失敗需要對比7、13、19三次即父節點所在層數(就是圓形節點所在層數嗎？)

順序查找的優化(被查概率不相等)：

每個關鍵字的查找概率不相等，假如查找成功的概率大就把被查概率大的放前面有助于在查找成功時縮短ASL，但是此時數組的數據亂序，即可以提高查找成功的平均查找長度，但是查找失敗的情況需要從頭掃到尾才知道查找失敗了，即查找失敗的平均查找長度ASL非常大，故具體問題具體分析

不管怎么優化只要采用順序查找，時間復雜度就是O(n)

?

知識回顧：?

聽不懂在講什么。。。。。。。。。?