二分查找：零基礎也能學會的高效查找算法¶

你有沒有玩過“猜數字”遊戲？比如心裏想一個1到100之間的數字，別人每次猜一個數，你只需要說“大了”或“小了”，對方很快就能猜到。這個過程其實就是二分查找的思想——每次通過中間值縮小一半的範圍，快速定位目標。

什麼是二分查找？¶

二分查找（Binary Search），也叫折半查找，是一種在有序數組中快速定位目標元素的算法。它的核心思想是：通過不斷比較中間元素，將查找範圍“減半”，直到找到目標或確定不存在。

爲什麼需要有序數組？¶

假設數組是無序的，比如 [3, 1, 4, 2, 5]，當你猜中間數是4時，無法確定目標在左邊還是右邊（比如目標是1，4比1大，但左邊還有3和1，需要繼續比較左邊）。只有數組有序時，中間元素才能作爲“分界點”，通過比較大小直接判斷目標在哪一側。

二分查找的適用場景¶

二分查找雖然高效，但有明確的適用條件，不是所有場景都適用：

數據必須是有序的（升序或降序，最常見升序）。
數據量較大：當數據量n很大時（比如10000個元素），二分查找的效率比線性查找（逐個比較）高得多。
數據是靜態的：如果數據頻繁插入、刪除或修改，維護有序數組的成本會很高，此時二分查找的優勢會被抵消。
需要快速查找：適用於“一次構建、多次查詢”的場景（如字典、配置文件）。

查找過程舉例¶

以數組 [1, 3, 5, 7, 9, 11, 13] 爲例，目標是找 7：

初始範圍：左指針 left=0（指向1），右指針 right=6（指向13）。
第一次中間值：mid = (0+6)//2 = 3（數組索引3的元素是7？不對，這裏索引3是7嗎？等一下，數組是 [1(0), 3(1), 5(2), 7(3), 9(4), 11(5), 13(6)]，所以 mid=3 正好是7！直接找到，返回索引3。

再舉一個找9的例子：
- 初始 left=0，right=6，mid=3（元素7）。
- 因爲9 > 7，目標在右半部分，所以 left = mid + 1 = 4。
- 新範圍：left=4，right=6，mid=(4+6)//2=5（元素11）。
- 因爲9 < 11，目標在左半部分，所以 right = mid - 1 = 4。
- 新範圍：left=4，right=4，mid=4（元素9），找到目標，返回索引4。

代碼實現（迭代法）¶

用Python實現一個基礎的二分查找函數，初學者可以直接參考：

def binary_search(nums, target):
    left = 0
    right = len(nums) - 1  # 初始右指針指向最後一個元素
    while left <= right:  # 範圍有效：左指針 <= 右指針
        mid = (left + right) // 2  # 計算中間位置（向下取整）
        if nums[mid] == target:
            return mid  # 找到目標，返回索引
        elif nums[mid] < target:
            left = mid + 1  # 目標在右半部分，左指針右移
        else:
            right = mid - 1  # 目標在左半部分，右指針左移
    return -1  # 遍歷結束未找到，返回-1

關鍵細節解釋：¶

循環條件：left <= right 確保當範圍只剩一個元素時（left=right），仍能判斷該元素是否爲目標。
中間值計算：mid = (left + right) // 2，Python中整數除法自動向下取整，確保範圍正確縮小。
邊界處理：如果數組爲空（len(nums)=0），直接返回-1；如果目標不存在，最終 left > right 時返回-1。

時間與空間複雜度¶

時間複雜度：每次查找範圍減半，次數爲 log₂n（n爲數組長度），即 O(log n)。例如n=10000時，最多需要14次查找（2¹⁴=16384）。
空間複雜度：迭代實現僅用了left、right、mid三個變量，爲 O(1)（常數級）。

常見問題與解決¶

數組中有重複元素怎麼辦？
基礎二分查找可能返回任意一個重複元素的位置。若需找到所有重複元素，可在找到目標後，向左右擴展遍歷。
數組長度爲1時如何處理？
直接進入循環判斷：left=0，right=0，mid=0，比較後返回或結束。
找不到目標時返回-1：明確告知用戶未找到，避免返回隨機值。

總結¶

二分查找的核心是“減治”——通過每次比較中間值，快速縮小查找範圍。記住以下關鍵點：
- 前提：數組必須有序。
- 優勢：大數據量下效率極高（O(log n)），空間佔用小（O(1)）。
- 場景：靜態有序數據的快速查找（如字典、配置表）。

只要理解“中間值比較+範圍調整”的邏輯，二分查找其實很容易掌握。接下來可以嘗試自己編寫迭代版本的二分查找，解決類似“在有序數組中找特定數”的問題！

二分查找：二分查找的適用場景，零基礎也能學會