申論題

Iterative Binary Search
python
複製程式碼
def binary_search_iterative(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

# 測試例子
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 5
print(binary_search_iterative(arr, target))  # 輸出: True

target = 11
print(binary_search_iterative(arr, target))  # 輸出: False
Recursive Binary Search
python
複製程式碼
def binary_search_recursive(arr, target, left, right):
    if left > right:
        return False
    mid = (left + right) // 2
    if arr[mid] == target:
        return True
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

# 測試例子
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 5
print(binary_search_recursive(arr, target, 0, len(arr) - 1))  # 輸出: True

target = 11
print(binary_search_recursive(arr, target, 0, len(arr) - 1))  # 輸出: False
簡單說明
Iterative Binary Search:
我們使用 while 迴圈來不斷縮小搜尋範圍，直到找到目標值或範圍無效（left > right）。
在每次迭代中計算中點 mid，並根據 target 值與 arr[mid] 比較結果來調整搜尋範圍。
Recursive Binary Search:
我們使用遞迴函數來進行二元搜尋，每次遞迴呼叫都會更新搜尋範圍的左右邊界 left 和 right。
在每次遞迴中計算中點 mid，並根據 target 值與 arr[mid] 比較結果來決定進行下一次遞迴的範圍。
測試範例
這些函數已經包含了測試例子，可以用來驗證實現的正確性。你可以根據需要調整測試數列和目標值。