演算法系列 · 第 13 關 · 搜尋

線性搜尋 Linear Search

最單純的搜尋 —— 從頭一個一個比,直到找到。任何資料都能用,不用先排序。

線性搜尋就是「一個一個看過去」:從第一個開始比,是目標就回傳位置,不是就看下一個,直到找到或看完整排。笨,但最萬用 —— 資料完全不用先排序、任何順序都能找,這是二分搜尋做不到的。代價是最壞要看完全部,O(n)。

核心觀念

從頭到尾逐一比對 —— 拿目標跟每個元素比,相等就是找到。

找到就停 —— 一旦命中立刻回傳位置,不用再看後面。

看完都沒有就是沒有 —— 回傳「找不到」(例如 -1 或 None)。

完全不需要排序 —— 這是它跟二分搜尋最大的差別,也是它的價值。

O(1)最好情況 —— 目標剛好在第一個,比一次就中。

O(n)平均 / 最壞 —— 目標在中間、最後、或根本不在,要看大約 n 個。

O(1)空間 —— 只用一個索引變數,不佔額外空間。

別看它笨,它有二分搜尋沒有的本事:不用排序、能用在任何順序的資料上,連鏈結串列、串流這種不能隨機跳的結構也能找。

資料沒排序、或只找一次 —— 用線性。為了找一次而先排序(O(n log n))不划算。

資料已排序、要重複找很多次 —— 用二分,每次 O(log n) 才划算。

資料很小(幾十筆) —— 線性就好,簡單、不容易寫錯。

不是陣列(鏈結串列、串流) —— 只能線性,沒辦法隨機跳到中間。

🔑

一把一把插進去試,直到有一把打得開 —— 沒有捷徑,就是逐一嘗試。

📚

從最左邊一本一本看書名,看到要找的那本為止。

🎒

一格一格伸手摸,摸到為止 —— 東西沒有固定位置,只能全翻。

一排沒有排序的資料 [4, 8, 1, 9, 3, 7, 2, 6]。紫色是正在比的那格、淡掉的是比過不是的、綠色是命中。因為沒排序,只能從頭掃 —— 選一個目標,按「下一步」數數看要比幾次。

找目標:

從最基本的逐一比對、內建 in / index,到找全部、依條件找、鏈結串列搜尋、哨兵優化。

❌ 對已排序的大資料還用線性 —— 已排序又要重複查,用二分 O(log n) 快多了。

❌ index() 找不到沒接 ValueError —— 先用 in 確認,或包 try / except。

❌ 要找「全部」卻找到一個就 return —— 要全部就別提早停,把符合的收集起來。

❌ 邊掃邊改陣列 —— 索引會錯位、會漏,先掃完再改。

把答案打到對話裡,我幫你對。