Big-O符號線性和二進制搜索

Question

在Big-O符號方面，線性搜索是x^n，但二進制搜索是什麼？我不是100％的線性搜索是正確的。

Answer 1

線性搜索意味着您將不得不遍歷元素列表，直到找到要查找的元素。

舉例來說，如果你有一個元素[1, 3, 5, 7, 9, 11]清單和你正在尋找11你會被第一個元素，那麼第二個元素，依此類推，在這種情況下將需要6次迭代開始。

一般來說，我們可以說在最壞的情況下，你將不得不遍歷整個列表;所以需要n次迭代，其中n是列表上元素的數量。

所以我們說線性搜索算法是O(n)。

在二進制搜索的情況下，啓動列表的中間元素：

• 案例1：我們正在尋找的數量是一樣的中間元素上的數字：我們是完成了！
• 案例2：我們搜索的編號較小：我們只搜索中間元素之前的元素。
• 案例3：我們搜索的編號較大：我們只會搜索後續元素。

在我們的例子中，我們正在尋找數爲11和中間元素是5;自11> 5以來，我們只會在大於5的元素的子列表上搜索，即[7, 9, 11]。

現在，我們將繼續這樣做，直到找到我們正在搜索的元素，在這種情況下，只需要三次迭代就可以到達最後一個元素。

通常這種方法需要log(n)迭代;因此，該算法是O(log(n))。

請注意，後者只適用於排序列表。