遞歸二分搜尋法

3.1 遞歸二分搜尋法的運作原理

二分搜尋 — 是一種用來在排序陣列中查找元素的算法，運作原理是 "分而治之"。 它將目標元素與陣列中間的元素進行比較，然後決定在陣列的哪一半繼續搜尋。遞歸二分搜尋重複此過程，並自己呼叫自己，使用更新的陣列邊界。

算法步驟：

1. 比較目標元素與陣列中間的元素。
2. 如果中間元素與目標元素相符，返回它的索引。
3. 如果目標元素較小，則在陣列左半部分繼續搜尋。
4. 如果目標元素較大，則在陣列右半部分繼續搜尋。
5. 重複該過程，直到找到元素或耗盡陣列。

遞歸二分搜尋法的實現

Python 範例：

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1  # 基本情況: 未找到元素
            
    mid = (left + right) // 2  # 找到陣列中間值
            
    if arr[mid] == target:
        return mid  # 基本情況: 找到元素
    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 = 7
result = binary_search_recursive(arr, target, 0, len(arr) - 1)
print(f"元素找到於位置: {result}")  # 輸出: 元素找到於位置: 6
        

3.2 與迭代二分搜尋法的比較

迭代二分搜尋：

def binary_search_iterative(arr, target):
    left, right = 0, len(arr) - 1
            
    while left <= right:
        mid = (left + right) // 2
                
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return -1  # 元素未找到
        
# 使用範例：
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search_iterative(arr, target)
print(f"元素找到於位置: {result}")  # 輸出: 元素找到於位置: 6
        

比較：

實現簡單性：

• 遞歸算法通常更簡單且更短，但需要理解遞歸調用。
• 迭代算法使用循環，對初學者可能更易理解。

記憶體：

• 遞歸算法使用調用棧，可能會在大量數據時增加記憶體使用。
• 迭代算法使用恆定量的記憶體，這使得它在記憶體使用上更有效。

性能：

• 兩種算法的時間複雜度皆為 O(log n)。
• 遞歸算法可能較慢，特別是在遞歸深度很大時，因為有遞歸調用的開銷。

3.3 遞歸二分搜尋法的範例問題

遞歸二分搜尋是一個強大的算法，可以快速在排序陣列中找到元素。它基於 "分而治之" 的原則，並利用遞歸將問題分解為更小的子問題。

比較遞歸和迭代的方法顯示出它們各自在不同問題上的優勢和劣勢。理解這些算法及其應用，能有效地解決搜尋問題。

例如，如下問題：

在排序陣列中搜尋元素：

在數字陣列中搜尋特定元素，例如評估測試，通過排序鍵在資料庫中搜尋等。

檢查元素是否存在：

檢查列表中是否存在特定目標，例如允許用戶的列表，ID等。

搜尋最近的值：

在陣列中查找與指定值最接近的元素，例如在搜尋最近的商店、車站等時。

最佳化：

解決需要在排序陣列中搜尋最佳值的問題，例如，尋找函數中的最小或最大值。