用Python实现二分查找算法

二分查找算法，也称为折半查找算法，是一种高效的查找算法，适用于有序数组。它的基本思想是从数组的中间元素开始，将要查找的值与中间元素进行比较，根据比较结果选择继续查找左半部分还是右半部分，直到找到目标元素或者查找范围为空。

以下是使用Python实现的二分查找算法：

def binary_search(arr, target):
    left = 0
    right = 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

上述代码中，binary_search函数接受一个有序数组arr和一个目标值target作为参数。初始化左指针left为数组的第一个元素的下标，右指针right为数组的最后一个元素的下标。进入循环，当left小于等于right时，计算中间元素的下标mid。若中间元素等于目标值，则直接返回mid。若中间元素小于目标值，说明目标值在右半部分，将左指针left移动到mid+1的位置。若中间元素大于目标值，说明目标值在左半部分，将右指针right移动到mid-1的位置。继续循环直到找到目标元素或者查找范围为空。若循环结束仍未找到目标元素，则返回-1表示未找到。

下面是使用示例：

arr = [2, 4, 7, 9, 12, 15, 19, 21, 23]
target = 9

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

输出结果为：

目标元素在数组中的下标为 3

这个例子中，有序数组arr包含了一些整数，目标值target为9。调用binary_search函数，最终找到目标元素9在数组中的下标为3。

二分查找算法的时间复杂度为O(log n)，其中n为数组的长度。这是因为每次比较后，查找范围会缩小一半，所以最坏情况下需要进行log2 n次比较。相比于线性查找算法的时间复杂度O(n)，二分查找算法是一种高效的查找方法。