Python Binary Search Algorithm

以對數 O(log n) 時間搜尋排序清單。在 Python 中運行並理解二分搜索，包括逐步邏輯、邊緣情況和最佳化。

概述

二分搜尋是一種在排序清單中尋找項目的非常有效的演算法。 Unlike linear search which scans every element sequentially in O(n) time, binary search works by repeatedly dividing the search interval in half.

搜索首先检查数组的中间元素。如果目標值與中間元素匹配，則傳回其位置。如果目標較小，演算法將搜尋範圍縮小到下半部；如果目標較大，則會將其縮小到上半部。重複此過程，直到找到元素或子數組大小降至零。

為了在 Python 中實現二分搜索，我們使用兩個指標（低和高）來追蹤活動搜尋邊界。由於每一步搜尋空間都會減少一半，因此該演算法的執行時間為 O(log n)，非常適合海量資料庫。

程式碼和執行輸出

A standard iterative binary search implementation that returns the index of a target element in a sorted list.

binary_search.py

在編輯器中嘗試

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]
        
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
            
    return -1

# Sorted test dataset
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_val = 23

index = binary_search(data, target_val)
print(f"Dataset: {data}")
print(f"Target: {target_val}")
if index != -1:
    print(f"Target found at index: {index}")
else:
    print("Target not found in dataset")

端子輸出

Dataset: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target: 23
Target found at index: 5

逐步實施

Query indexing and searching in database tables
尋找連續數學範圍內的閾值或邊界值
Autocomplete and search functions in text fields

常見問題解答

是否必須對清單進行排序才能進行二分搜尋？

是的，二分查找嚴格依賴被排序的元素。如果清單未排序，比較邏輯就會中斷，您必須先對清單進行排序或使用線性搜尋。

為什麼使用迭代二分搜尋而不是遞歸二分搜尋？

雖然遞歸二分搜尋很優雅，但迭代二分搜尋在生產中通常是首選。 The iterative approach runs in O(1) auxiliary space, whereas recursive search takes O(log n) space due to the call stack, risking stack overflow on extremely large inputs.