線性搜索跳轉米的地方

Question

這裏是我的僞代碼：

LinearSearch(List, key, m): 
    while (m < List.length): 
     if (m==key):    // key is found 
      return m 
     else if (m < key):  // key is larger than index 
      m = m + m 
     else:     // key is smaller than index 
      m = m - 1 
    return NIL 

但我不認爲這是正確的，因爲它似乎不是正確的，如果關鍵是List.length之間 - m和List.length。

請問誰能告訴我有什麼問題？

我也想該算法的時間複雜度，在三種情況：

worstcase when successful search 
worst case when unsuccessful search 
average case 

謝謝

Answer 1

你比較m到key幾次。你應該比較list[m]到key。

此外，如果m從0開始，它永遠不會是0（0 + 0 = 0）。

另一個問題是你列出的問題。說list是{1 2 3 4 5 6 7 8 9},key是9，你開始在m=1。 m將變成2，然後是4，然後是8. List[m]仍然小於關鍵字，所以m再次翻倍到16，並且在那一點退出循環，因爲m不再小於列表的長度。有幾種方法可以解決這個問題，一旦你理解了你遇到的問題，這些方法都不會很複雜。