在我們的日常學習和生活中，經常會遇到“找東西”的場景。比如在字典裏查一個單詞，在電話簿裏找一個電話號碼，或者在列表裏找某個商品的價格。這些“找東西”的過程，在計算機裏就對應着查找算法。查找算法有很多種，今天我們就從最簡單的線性查找開始，逐步瞭解更高效的二分查找，看看它到底快在哪裏。

一、什麼是線性查找？¶

線性查找（也叫順序查找）是最基礎的查找方法，它的原理非常簡單：從頭到尾逐個檢查數據，直到找到目標元素。

舉個例子：假設我們有一個數組 [2, 5, 8, 12, 16]，要找數字 8。

• 第一步：檢查第一個元素 2，不是目標；
• 第二步：檢查第二個元素 5，不是目標；
• 第三步：檢查第三個元素 8，找到了！

如果目標元素不存在，線性查找會遍歷整個數組後才結束。

線性查找的特點：¶

• 時間複雜度：
• 最好情況：目標元素就在第一個位置，只需 1 次查找（記爲 O(1)）；
• 最壞情況：目標元素在最後一個位置，或不存在，需要遍歷整個數組（記爲 O(n)，其中 n 是數據量）；
• 平均情況：還是 O(n)，因爲平均需要檢查一半的數據。

比如，當數據量是 10000 個時，線性查找最壞可能需要 10000 次查找，這在大數據量下效率非常低。

二、二分查找：從“逐個檢查”到“對半排除”¶

線性查找的缺點是效率低，尤其是數據量大的時候。有沒有更快的方法呢？當然有，這就是二分查找（Binary Search）。

二分查找的前提：¶

二分查找只能在有序數組中使用（比如從小到大或從大到小排列的數組）。如果數組是無序的，二分查找就不適用了。

二分查找的原理：¶

它的核心思想是“每次排除一半的數據”。具體來說：
1. 先找到數組的中間位置，比較中間元素和目標元素；
2. 如果中間元素等於目標，直接找到；
3. 如果中間元素比目標大，說明目標在中間元素的左邊，接下來只需要在左半部分繼續查找；
4. 如果中間元素比目標小，說明目標在中間元素的右邊，接下來只需要在右半部分繼續查找；
5. 重複上述步驟，直到找到目標或確定不存在。

用例子理解二分查找：¶

還是剛纔的有序數組 [2, 5, 8, 12, 16]，現在找數字 8。

• 第一次查找：數組長度是 5，中間位置是第 2 個元素（索引 2，數值 8）。正好等於目標，直接找到！

再舉一個複雜點的例子：找 12。

• 第一次查找：中間位置是第 2 個元素（數值 8）。因爲 8 < 12，所以目標在右半部分，剩下的數組是 [12, 16]；
• 第二次查找：新數組長度是 2，中間位置是第 1 個元素（數值 12）。等於目標，找到！

二分查找的時間複雜度：¶

每次查找都會排除一半的數據，所以查找次數與數據量的“對數”相關。時間複雜度記爲 O(log n)（log 是對數，這裏默認以 2 爲底）。

比如：
- 數據量 n=1000 時，log₂(1000) ≈ 10（即最多 10 次查找）；
- 數據量 n=10000 時，log₂(10000) ≈ 14（最多 14 次查找）；
- 數據量 n=1000000 時，log₂(1000000) ≈ 20（最多 20 次查找）。

三、二分查找比線性查找快多少？¶

我們用具體數據對比一下：

關鍵結論：當數據量 n 越大時，二分查找的速度優勢越明顯。比如 n=100 萬時，二分查找只需 20 次，而線性查找要 100 萬次，差距高達 5 萬倍！

四、什麼時候用二分查找？什麼時候用線性查找？¶

二分查找適用場景：¶

• 數據是有序的（如已排序的列表、數組）；
• 數據量較大（此時效率優勢更明顯）；
• 需要頻繁查找（二分查找的“準備時間”是排序，但如果是固定有序數組，後續查找很高效）。

線性查找適用場景：¶

• 數據是無序的（無法使用二分查找）；
• 數據量非常小（比如只有幾個元素，線性查找反而更簡單，無需額外準備）；
• 數據是動態變化的（頻繁插入/刪除會破壞有序性，線性查找更靈活）。

五、總結：二分查找的核心價值¶

二分查找是數據結構中經典的“高效查找技巧”，它通過“對半排除”的策略，將查找次數從 O(n) 降到 O(log n)，在大數據量下效率遠超線性查找。但要記住：有序數組是二分查找的前提，如果數據無序，就只能用線性查找。

對於初學者來說，理解二分查找的“排除一半”邏輯，掌握它的時間複雜度分析，以及和線性查找的對比，就能在實際問題中根據數據特點選擇合適的查找方法。隨着數據量的增長，二分查找的優勢會越來越突出，這也是它成爲算法面試和實際開發中高頻考點的原因。