（必做题）用分治策略写出并实现二分检索算法，要求如下： (1) 选择合适的数据结构来表示问题中的数列； (2) 根据分治法的基本原理，写出求解二分检索的算法； (3) 上机运行程序，验证算法的正确性，并分析算法的时空复杂性。

二分查找，也称为折半搜索，是一种在有序数组中寻找特定元素的搜索算法。以下是用Python实现的一个基本版本：

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # 使用整数除法避免浮点误差
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return -1  # 如果目标不在数组中，返回-1

# 示例数据结构：列表（list）
# 数组已经假设是排序好的
data = [1, 3, 5, 7, 9, 11, 13]
target = 9

result = binary_search(data, target)
if result != -1:
    print(f"找到了目标 {target}，其索引为 {result}")
else:
    print("目标未找到")

# 分析：
# - 时间复杂度：O(log n)，这是因为每次比较都将搜索范围减半。n是数组长度。
# - 空间复杂度：O(1)，因为只使用了几个变量，不随输入大小变化。

#