"""
二分查找 — 在有序数组中查找目标值
时间复杂度 O(log n)
"""

def binary_search_recursive(arr, target, left, right):
    """递归版二分查找"""
    if left > right:
        return -1

    mid = left + (right - left) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search_recursive(arr, target, left, mid - 1)
    else:
        return binary_search_recursive(arr, target, mid + 1, right)

def binary_search_iterative(arr, target):
    """迭代版二分查找"""
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            right = mid - 1
        else:
            left = mid + 1

    return -1

if __name__ == "__main__":
    arr = [1, 3, 5, 7, 9, 11, 13, 15]
    target = 7

    idx1 = binary_search_recursive(arr, target, 0, len(arr) - 1)
    idx2 = binary_search_iterative(arr, target)

    print(f"数组: {arr}")
    print(f"查找 {target}: 递归版结果索引={idx1}, 迭代版结果索引={idx2}")