Linear Search線性搜尋
一個一個看，無序資料唯一的選擇。
用在：小資料、無序資料、只找一次
01為什麼需要它
程式啟動時讀一個幾十行的設定檔，要找某個欄位的值。要不要先建索引、排序、用雜湊表？
為什麼用它幾十筆資料從頭看到尾，只要微秒等級的時間。排序或建雜湊表本身就得把每一筆都處理一遍，只找一次的話，建置成本一定比直接掃一遍高。資料小又只找一次，一個一個看就是最快的方法。
一份剛寫完的日誌檔，順序是時間，內容沒有任何索引。要找出第一次出現 ERROR 的那一行。
為什麼用它資料沒有依你要找的東西排序，也不會重複查很多次。這種情況沒有捷徑，順著掃是唯一的選擇，而且找到就能停。
手上有一份 5 個元素的「最近用過的檔案」清單，每次開檔都要查它在不在清單裡。要用雜湊表嗎？
為什麼用它元素很少時，線性掃描的常數比雜湊小：不用算 hash、記憶體連續、CPU 快取友善。5 個元素最多比 5 次，不值得為它另外維護一個雜湊表，還要保持兩者同步。
看到這些關鍵字就想到它：資料無序、資料很小、只查一次、找到就停、不值得先排序或建索引。
02核心概念
線性搜尋是最直接的搜尋：從第一個元素開始，一個一個和目標比，相等就回傳位置，掃完都沒有就回傳「不存在」。它不需要資料有任何性質，不需要排序、不需要額外空間，任何可以逐一走訪的東西（陣列、鏈結串列、檔案的每一行）都能用。
成本是 O(n) 時間、O(1) 額外空間：最好情況第一格就中，比 1 次；最壞情況比 n 次（目標在最後一格或不存在）；目標存在且在每個位置的機率相同時，平均比 (n+1)/2 次，仍然是 O(n)。這個數字本身不是問題，問題是它會不會被重複很多次。查一次 O(n) 很便宜；查 m 次就是 O(mn)，這時才需要先花 O(n log n) 排序換取每次 O(log n) 的二分搜尋，或花 O(n) 建雜湊表換取每次平均 O(1)。優化是用建置成本換查詢成本，只查一次的資料不值得。
另一個容易忽略的點是常數。線性掃描的迴圈極簡單，記憶體連續存取，CPU 分支預測和快取都很友善。元素在幾十個以內時，它常常比雜湊表快，因為省掉了算 hash 和隨機記憶體存取。所以「小就直接掃」是真實世界的做法，不是偷懶：例如 Rust 標準函式庫的 BTreeMap，每個節點最多放 11 個 key，在節點裡找 key 用的就是線性搜尋。
和相鄰工具的分界：資料已經有序（而且能隨機存取），直接二分搜尋，查一次也划算；資料無序但會重複查，先排序再二分，或建雜湊表；資料無序又只查一次，或資料小到建結構的成本都划不來，就用線性搜尋。另外，沒有任何結構可利用時，最壞情況每一格都得看過才能確定目標不在，所以 O(n) 已經是下限，不是寫得不好。學它的重點不是演算法本身，而是知道什麼時候不需要更好的演算法。
03演算法步驟
- 1從索引 0 開始，
i = 0。 - 2只要
i < n，就比較nums[i]和目標。相等就回傳i，這是唯一的成功出口。 - 3不相等就
i += 1，回到上一步。 - 4
i到達n（包括陣列是空的、一開始n = 0）表示全部看過都沒有，回傳-1。 - 5需要「所有符合的位置」時，不要提前回傳，把每個符合的
i收進清單，掃完再回傳。
04互動示範
無序的 10 個數字裡找 46，再切換成找不存在的 40，看最壞情況比了幾次。下方表格列出不同 n 時，線性搜尋和二分搜尋最壞要比幾次，二分的前提是資料已經排好。
| n | 線性 n | 二分 ⌈log₂(n+1)⌉ |
|---|---|---|
| 10 | 10 | 4 |
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
| 1,000,000,000 | 1,000,000,000 | 30 |
n = 10 時只差 6 次，為了省這幾次先排序（O(n log n)）反而更慢。n = 10 億時線性最壞要比 10 億次，二分只要 30 次，所以同一份資料要查很多次時，先排序一次再二分才划算。
05程式碼
基本版、回傳所有符合位置的版本，以及每一輪省一次邊界檢查的哨兵法。三段都是 O(n) 時間，差在回傳什麼和迴圈裡做幾次比較。最後附上語言內建的線性搜尋：Python 的 in、list.index，C++ 的 std::find。
# 線性搜尋：從頭掃到尾，找到就回傳索引，沒有就回傳 -1
def linear_search(nums, target):
for i, x in enumerate(nums):
if x == target:
return i
return -1
# 變形一：回傳所有符合條件的位置（條件用函式傳入）
# 條件是任意函式時，每個元素都得檢查一次，O(n) 已經是最好
def find_all(items, pred):
return [i for i, x in enumerate(items) if pred(x)]
# 變形二：哨兵法。暫時把目標放在尾端，保證一定找得到，
# 迴圈裡每一輪就省掉一次 i < n 的邊界檢查
# 這是 C 這類語言的技巧；在 Python 裡通常比上面的 for 迴圈還慢
def sentinel_search(nums, target):
n = len(nums)
nums.append(target) # 哨兵（暫時改動 nums）
i = 0
while nums[i] != target:
i += 1
nums.pop() # 還原
return i if i < n else -1 # 停在哨兵上 = 原本沒有
if __name__ == "__main__":
data = [17, 4, 29, 8, 51, 23, 12, 46, 3, 35]
print(linear_search(data, 46)) # 7
print(linear_search(data, 40)) # -1
print(find_all(data, lambda x: x % 2 == 0)) # [1, 3, 6, 7]
print(sentinel_search(data, 46)) # 7
print(sentinel_search(data, 40), len(data)) # -1 10（哨兵已移除）
# 內建的 in 和 list.index 也是線性搜尋；index 找不到會丟 ValueError
print(40 in data, data.index(46)) # False 706練習題
- LeetCode 2057Smallest Index With Equal Value（找第一個，找不到回傳 -1）Easy
- LeetCode 2108Find First Palindromic String in the Array（條件換成函式，找到就停）Easy
- LeetCode 2942Find Words Containing Character（回傳所有符合的位置）Easy
- LeetCode 1779Find Nearest Point That Has the Same X or Y CoordinateEasy
- LeetCode 1848Minimum Distance to the Target Element（從 start 往兩邊找）Easy
- LeetCode 1Two Sum（先對每個數線性搜尋另一半，再想為什麼要換雜湊表）Easy