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

二分查找（Binary Search），也称为折半搜索，是一种在有序数组中寻找特定元素的搜索算法。它通过将数组分成两部分来不断缩小搜索范围，直到找到目标元素或者确定元素不存在。

(1) 数据结构：为了方便二分查找，我们通常会使用顺序表（数组）来存储数据，因为顺序表提供随机访问的能力，非常适合支持快速定位。

# Python 示例中的数据结构
class BinarySearchArray:
    def __init__(self, arr):
        self.array = sorted(arr)

(2) 算法实现：

def binary_search(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  # 如果没找到，返回-1

# 调用函数示例
arr = [1, 3, 5, 7, 9]
target = 5
result = binary_search(arr, target)
if result != -1:
    print(f"找到了，索引位置：{result}")
else:
    print("未找到")

(3) 验证与复杂度：
上机运行上面的程序，输入一些已排序的数字和目标值，可以看到每次循环都将搜索范围减半，直至找到目标或范围为空。时间复杂度为O(log n)，n为数组长度，因为每一次迭代都会排除一半的可能性。空间复杂度为O(1)，因为我们只使用了几个变量来保存中间结果，不随输入大小变化。