Python 二分查找算法

1. 简介

二分查找，也称为折半查找，是一种在有序数组中查找特定元素的算法。其原理是将待查找区间的中间元素与目标元素进行比较，将待查找区间缩小为一半，并继续在缩小后的区间中查找，直到找到目标元素或者确定目标元素不存在为止。

二分查找算法的时间复杂度为O(log n)，效率较高，在大规模数据的查找中被广泛应用。

2. 算法实现

下面给出一个简单的 Python 实现二分查找的示例代码：

def binary_search(arr, low, high, target):
    if high >= low:
        mid = (high + low) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            return binary_search(arr, low, mid - 1, target)
        else:
            return binary_search(arr, mid + 1, high, target)
    else:
        return -1

3. 算法流程解析

二分查找算法的核心思想是通过不断缩小待查找区间来寻找目标元素。下面对上述示例代码进行详细解析：

将目标元素 target 与待查找数组 arr 的中间元素 arr[mid] 进行比较。如果相等，则返回 mid，表示找到目标元素所在的索引。
如果 arr[mid] > target，说明目标元素位于数组的左半部分，我们继续在 arr 的左半部分进行查找，即在 low 到 mid - 1 的区间内递归调用 binary_search 函数。
如果 arr[mid] < target，说明目标元素位于数组的右半部分，我们继续在 arr 的右半部分进行查找，即在 mid + 1 到 high 的区间内递归调用 binary_search 函数。
如果 high 小于等于 low，表示待查找区间为空，即目标元素不存在于数组中，返回 -1。

4. 示例测试

为了验证二分查找算法的正确性，我们可以编写一些示例测试代码来测试该算法的性能和准确性。下面给出一个使用示例测试代码的例子：

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
result = binary_search(arr, 0, len(arr)-1, target)

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

执行以上代码，输出结果为：