二分查找算法

简介

二分查找，也叫折半查找，是一种常见的查找算法。它的时间复杂度为O(log n)，相较于暴力查找的O(n)，具有更高的效率。二分查找的前提是查找的元素是有序的。

二分查找算法可以应用于寻找数值、确定数值上下边界等一系列需要数值二分的问题。

实现

1. 首先确定查找范围的左右端点，对于有序数组，左端点为0，右端点为数组长度减1。
2. 确定中间元素的索引：mid = (left + right) // 2。将中间元素与目标元素进行比较，如果中间元素小于目标元素，则目标元素在中间元素右侧，需要在右侧查找；反之，在左侧查找。
3. 更新查找范围的左右端点。如果目标元素在右侧，left = mid + 1；反之，right = mid - 1。重复步骤2 – 3，直到找到目标元素或者查找范围为空。

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:
            left = mid + 1
        else:
            right = mid - 1
    return -1    # 如果没找到，返回-1

示例

示例1：查找指定元素

假设有一个有序数组arr = [1, 3, 4, 6, 7, 8, 10]，现在要查找元素target = 4。请使用二分查找找到该元素的位置。

arr = [1, 3, 4, 6, 7, 8, 10]
target = 4
result = binary_search(arr, target)
if result != -1:
    print("目标元素在索引%d处" % result)
else:
    print("目标元素不存在")

程序运行结果为：

目标元素在索引2处

示例2：寻找上下边界

假设有一个有序数组arr = [2, 3, 3, 5, 7, 8, 9, 9, 9, 10, 11]，现在要查找元素target = 9出现的上下边界。请使用二分查找找到这两个边界的位置。

def left_bound(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    if left >= len(arr) or arr[left] != target:
        return -1
    return left

def right_bound(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid - 1
    if right < 0 or arr[right] != target:
        return -1
    return right

arr = [2, 3, 3, 5, 7, 8, 9, 9, 9, 10, 11]
target = 9
lb = left_bound(arr, target)
rb = right_bound(arr, target)
print("上边界：%d，下边界：%d" % (lb, rb))

程序运行结果为：

上边界：6，下边界：8

注意事项

1. 二分查找算法的前提是有序数组。如果数组无序，需要先进行排序。
2. 对于小数据量的查找，使用暴力查找可能比二分查找效率更高，因为二分查找有固定的常数时间。
3. 当目标元素多次出现时，二分查找只能找到其中一个位置。如果需要找到所有位置，可以使用特殊的左右边界查找方法。