[音樂播放] DOUG LLOYD：線性 搜索是一種算法，我們 可用來查找在數組中的元素。 算法召回 是一步一步的設置 的用於完成任務的指令。 

線性搜索 算法的工作方式如下。 跨越陣列迭代從左 沒錯，找指定的元素。 

在偽代碼中，這是一個更 蒸餾版本的這句話， 如果第一元件是什麼 你要尋找的，可以停止。 否則，移動到下一個元件和 繼續下去，一遍又一遍，直到找到 元素，或者你沒有。 因此，我們可以用線性 搜索算法，例如， 找到目標值 九裡這陣。 好了，我們從頭開始。 如果這就是我們 尋找，我們可以停止。 這不是，我們不是在尋找11。 所以否則，移動到下一個元素。 

所以，我們就來看看23。 23，我們在尋找什麼？ 哦，不，所以我們就移動到下一個 元件，並且下一個元素， 我們繼續經歷 這個過程中一遍又一遍 以上，直到我們的土地 在這樣的情況下。 

九是我們要找的， 和該陣列的這些元素 是，它的值是9。 因此，我們找到了我們 尋找，我們可以停下來。 線性搜索有 完成後，成功。 

但有關，如果我們要尋找什麼 一個元素，這不是在我們的數組。 是否線性搜索仍然有效？ 那麼肯定。 因此，我們重複這個過程 起始於第一元件。 如果這就是我們 尋找，我們可以停止。 它不是。 否則，我們進入下一個元素。 

但是我們可以不斷的重複這個過程， 檢查反過來每個元素， 希望我們找到了50號。 但我們不會知道 我們已經找到了50號 或者，如果我們沒有，直到我們已經加強 在陣列上的每一個元素。 

只有當我們已經做了 這並拿出短， 我們可以得出結論： 50不數組中。 這樣一來，線性搜索 算法，那麼它失敗了，本身。 但不是在某種意義上說，它 是不成功的在做什麼 我們要求它做的事情。 

這是不成功的作為 就像它沒有找到50， 但50並沒有到數組中。 但是，我們已經徹底搜查 通過每一個元素 所以，雖然我們沒有發現 任何事情，線性搜索仍 成功，即使 元素不是陣列中。 

那麼什麼是最壞的情況下 方案與線性搜索？ 那麼我們來看看通過 每一個元件， 要么是因為目標元素 是陣列的最後一個元素， 或者我們正在尋找的元素不 實際存在陣列中的。 什麼是最好的情況？ 嗯，我們可能會發現 元素立刻。 有多少元素和 我們接著來看看 在最好的情況下， 如果我們尋找它 我們發現它在開始的時候？ 我們可以立即停止。 

這是什麼說的 線性搜索的複雜性？ 井在最壞的情況下，我們有 看看每一個元素。 而且使其在鄰 N，在最壞的情況下。 

在最好的情況下，我們要 馬上找到的元素。 等運行在1歐米加。 

我是道格·勞埃德。 這是CS50。