返回值应插入位置的索引的二进制搜索

二进制搜索（Binary Search）是一种在有序数组中查找特定元素的搜索算法。其基本思想是通过每次比较数组中间元素与目标值，逐步缩小搜索范围，直到找到目标值或确定目标值不存在。

基础概念

有序数组：二进制搜索要求数组是有序的。
中间索引：每次搜索时，取数组的中间索引 mid = (low + high) / 2。
比较：比较中间元素与目标值，根据比较结果调整搜索范围。

优势

时间复杂度：O(log n)，比线性搜索快得多。
效率高：适用于大数据集。

类型

递归实现：通过递归调用自身来缩小搜索范围。
迭代实现：使用循环来缩小搜索范围。

应用场景

数据库索引：快速查找数据。
文件系统：快速定位文件。
算法竞赛：常见的问题解决方法。

示例代码（递归实现）

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

# 示例数组
arr = [2, 3, 4, 10, 40]
target = 10

result = binary_search(arr, target, 0, len(arr) - 1)

if result != -1:
    print("元素在索引 %d 处找到" % result)
else:
    print("元素不在数组中")

示例代码（迭代实现）

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# 示例数组
arr = [2, 3, 4, 10, 40]
target = 10

result = binary_search(arr, target)

if result != -1:
    print("元素在索引 %d 处找到" % result)
else:
    print("元素不在数组中")