用python实现二分查找算法

二分查找也叫折半查找，它是一种效率较高的查找算法，前提是数据必须是有序的。其基本思想是：将n个元素分成大致相等的两部分，取中间值与待查关键字进行比较，如果中间值大于待查关键字，则在左半部分继续执行查找；如果中间值小于待查关键字，则在右半部分继续查找，直到查找成功或者查找结束。

下面是Python实现二分查找算法的代码：

def binary_search(arr, left, right, x):
    # 如果左指针大于右指针，说明查找失败
    if left > right:
        return -1
    # 计算中间位置
    mid = (left + right) // 2
    # 如果中间位置的元素等于要查找的值，返回下标
    if arr[mid] == x:
        return mid
    # 如果中间位置的元素大于要查找的值，继续在左侧查找
    elif arr[mid] > x:
        return binary_search(arr, left, mid - 1, x)
    # 如果中间位置的元素小于要查找的值，继续在右侧查找
    else:
        return binary_search(arr, mid + 1, right, x)

# 测试
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x = 5
result = binary_search(arr, 0, len(arr)-1, x)

if result != -1:
    print("元素在数组中的下标为", str(result))
else:
    print("元素不在数组中")

输出结果为：

元素在数组中的下标为 4

说明在有序数组 `[1, 2, 3, 4, 5, 6, 7, 8, 9]` 中查找元素 `5` 的下标是 `4`。