减治法二分查找代码py

减治法二分查找也叫折半查找，是一种在有序数组中查找特定元素的搜索算法。这里有一个基础的Python实现示例：

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:
            right = mid - 1
        # 否则，在右半部分查找
        else:
            left = mid + 1
            
    # 如果没找到，返回-1
    return -1

# 测试
arr = [1, 3, 5, 7, 9]
target = 5
result = binary_search(arr, target)
if result != -1:
    print(f"Element found at index {result}")
else:
    print("Element not found in the array")

这个函数首先设置左右指针，然后进入循环，每次迭代都会检查中间元素。如果找到目标值，就返回其索引；如果目标值小于中间值，就在左半部分继续查找；反之，在右半部分查找。直到左指针大于右指针为止，说明未找到目标，返回-1。