1. 使用遞歸進行二分查找的 Python 程序

創建一個遞歸函數，并將搜索空間的 mid 與 key 進行比較。根據結果，要么返回找到鍵的索引，要么調用下一個搜索空間的遞歸函數。

# 用于遞歸二進制搜索的 Python 3 程序。
# 在注釋中可以找到對舊版 Python 2 所需的修改。# 如果存在，則返回 arr 中 x 的索引，否則返回 -1
def binary_search(arr, low, high, x):# Check base caseif high >= low:mid = (high + low) // 2# 如果元素本身存在于中間if arr[mid] == x:return mid# 如果元素小于中間值，則它只能出現在左子數組中elif arr[mid] > x:return binary_search(arr, low, mid - 1, x)# 否則該元素只能出現在右子數組中else:return binary_search(arr, mid + 1, high, x)else:# 元素不在數組中return -1# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 10# Function call
result = binary_search(arr, 0, len(arr)-1, x)if result != -1:print("元素存在于索引", str(result))
else:print("數組中不存在元素")

輸出

元素位于索引 3

時間復雜度：O（log n）

輔助空格：O（logn） [注意：遞歸創建調用堆棧]

2. 使用迭代進行二分查找的 Python 程序

這里我們使用 while 循環來繼續比較鍵并將搜索空間分成兩半的過程。

# 迭代二分搜索函數
# 如果存在，則返回給定數組 arr 中 x 的索引，
# 否則返回 -1
def binary_search(arr, x):low = 0high = len(arr) - 1mid = 0while low <= high:mid = (high + low) // 2# 如果 x 更大，則忽略左半部分if arr[mid] < x:low = mid + 1# 如果 x 較小，則忽略右半部分elif arr[mid] > x:high = mid - 1# 表示 x 出現在中間else:return mid# 如果我們到達這里，則該元素不存在return -1# 測試數組
arr = [ 2, 3, 4, 10, 40 ]
x = 10# 函數調用
result = binary_search(arr, x)if result != -1:print("元素存在于索引", str(result))
else:print("數組中不存在元素")

輸出

元素位于索引 3

時間復雜度：O（log n）

輔助空間：O（1）

3. 使用內置的 bisect 模塊進行二分查找的 Python 程序

分步方法：

• 代碼導入 bisect 模塊，該模塊提供對二分查找的支持。
• 定義binary_search_bisect() 函數的定義是將數組 arr 和要搜索的元素 x 作為輸入。
• 該函數調用 bisect 模塊的 bisect_left() 函數，該函數查找元素在排序數組 arr 中的位置，其中應插入 x 以保持排序順序。如果元素已存在于數組中，則此函數將返回其位置。
• 然后，該函數檢查返回的索引 i 是否在數組范圍內，以及該索引處的元素是否等于 x。
• 如果條件為 true，則函數返回索引 i 作為元素在數組中的位置。
• 如果條件為 false，則函數返回 -1，指示數組中不存在該元素。
• 然后，該代碼定義一個數組 arr 和一個要搜索的元素 x。
• 調用 binary_search_bisect（） 函數時，將 arr 和 x 作為輸入，返回的結果存儲在 result 變量中。
• 然后，代碼檢查結果是否不等于 -1，這表示該元素存在于數組中。如果為 true，則打印元素在數組中的位置。
• 如果結果等于 -1，則代碼將打印一條消息，指出該元素不存在于數組中。

import bisectdef binary_search_bisect(arr, x):i = bisect.bisect_left(arr, x)if i != len(arr) and arr[i] == x:return ielse:return -1# Test array
arr = [2, 3, 4, 10, 40]
x = 10# 測試數組
result = binary_search_bisect(arr, x)if result != -1:print("元素存在于索引", str(result))
else:print("數組中不存在元素")

輸出

元素位于索引 3

時間復雜度：O（log n）

輔助空間：O（1）