在編程或日常生活中，我們經常需要從一堆數據裏找到某個特定的元素，比如在通訊錄裏找朋友的電話，或者在成績單裏找同學的分數。這種“定位目標元素”的過程，就是查找算法要解決的問題。今天我們來聊聊兩種最基礎的查找算法：順序查找和二分查找，看看它們有什麼區別，以及哪個更快。
一、什麼是查找？¶
想象你在一本沒有目錄的電話簿裏找一個名字，只能一頁一頁翻；或者在一疊無序的試卷裏找某個人的分數，只能一張張看。這種“逐個檢查”的方式，就是查找的核心思想。但更高效的查找方式，需要更聰明的策略。
二、順序查找：最簡單的“逐個檢查”¶
1. 原理¶
順序查找（也叫線性查找）是最直接的方法：從數據的第一個元素開始，逐個與目標元素比較，直到找到目標或檢查完所有元素。
2. 例子（以數組爲例）¶
假設我們有一個數組 [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]，要找數字 16：
- 第1個元素：2 ≠ 16 → 繼續；
- 第2個元素：5 ≠ 16 → 繼續；
- 第3個元素：8 ≠ 16 → 繼續；
- 第4個元素：12 ≠ 16 → 繼續；
- 第5個元素：16 = 16 → 找到！
3. 優缺點¶
- 優點：簡單，不需要數據有序，適用於任何情況。
- 缺點：效率低。如果數據量很大（比如10000個元素），最壞情況要檢查所有元素，時間複雜度是 O(n)（n是數據量）。
三、二分查找：“分半”的高效查找¶
1. 原理¶
二分查找（也叫折半查找）要求數據必須是有序的（比如從小到大排列）。它的核心是“分半比較”：每次先找中間元素，如果中間元素等於目標，直接找到；如果中間元素比目標大，說明目標在左邊；如果中間元素比目標小，說明目標在右邊。然後重複這個過程，每次把查找範圍縮小一半。
2. 例子（以有序數組爲例）¶
還是上面的數組 [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]，要找數字 16：
- 第一步：數組範圍是 [0,9]（索引從0到9），中間位置 = (0+9)//2 = 4（第5個元素），中間元素是 16 → 正好等於目標，找到！
如果要找數字 23：
- 第一步：範圍 [0,9]，中間元素是16（索引4），23 > 16 → 目標在右邊，新範圍 [5,9]；
- 第二步：中間位置 = (5+9)//2 = 7（第8個元素），中間元素是56，23 < 56 → 目標在左邊，新範圍 [5,6]；
- 第三步：中間位置 = (5+6)//2 = 5（第6個元素），中間元素是23 → 找到！
3. 優缺點¶
- 優點：效率極高，時間複雜度是 O(log n)（比如n=1000，log₂1000≈10次，比順序查找快100倍）。
- 缺點：必須基於有序數組，如果數據無序，無法使用；實現時需注意邊界條件（比如中間位置計算、範圍調整）。
四、順序查找 vs 二分查找：區別總結¶
| 對比項 | 順序查找 | 二分查找 |
|---|---|---|
| 前提條件 | 不需要數據有序 | 必須是有序數組 |
| 查找方式 | 逐個比較，從左到右 | 分半查找，每次縮小一半範圍 |
| 時間複雜度 | O(n)（n爲數據量） | O(log n) |
| 實現難度 | 簡單，無邊界問題 | 需處理邊界條件（如中間位置） |
| 適用場景 | 數據量小、無序；頻繁增刪場景 | 數據量大、有序；靜態數據場景 |
五、哪個更快？¶
二分查找更快！ 當數據量很大時，二分查找的效率優勢非常明顯。比如：
- n=1000：順序查找最壞需1000次比較，二分查找只需約10次。
- n=10000：順序查找需10000次，二分查找只需約14次。
但注意：如果數據無序，二分查找無法使用，只能用順序查找。
六、總結¶
- 順序查找：簡單易用，適合小數據量、無序數據（或需要頻繁增刪的場景）。
- 二分查找：效率極高，適合大數據量、有序數據（但需先保證數據有序）。
選擇哪種算法，要根據數據的“有序性”和“規模”決定。有序大數據用二分，無序小數據用順序，這纔是最合理的選擇！