排序與搜尋
線性搜尋
線性搜尋是在清單裡找東西最樸實的辦法：從頭開始，一個接一個地逐項檢查，直到找到目標，或者走到末尾為止。這就像你在一份沒排序的來賓名單裡找朋友的名字——目光順著紙面，從上往下掃。
正因為它不做任何假設，線性搜尋對任何集合都管用，排沒排序都行，對任何能逐個元素走訪的結構也都適用——陣列、鏈結串列、一行一行讀取的檔案。這種普適性正是它的魅力：沒有任何要準備的，也沒有任何會出錯的。
代價是你可能得把所有元素都看一遍。最壞情況下目標是最後一個元素（或根本不存在），於是要做 n 次比較——時間為 O(n)。平均而言，若目標存在，大約掃描一半清單，仍是 O(n)。它不需要額外記憶體，空間為 O(1)。當資料無序，或規模小到不值得耍花招時，線性搜尋往往就是最對、也最簡單的選擇。
int linearSearch(const std::vector<int>& a, int target) {
for (int i = 0; i < (int)a.size(); ++i)
if (a[i] == target) return i; // found it
return -1; // not present
}可能每個元素都要看一遍，所以最壞情況是 n 次比較——O(n)。
如果資料已經有序，二分搜尋會大幅勝過線性搜尋——O(log n) 對 O(n)。只有當你要多次搜尋時才值得先排序；排一次序的代價是 O(n log n)。
又稱
另見