二分查找

二分查找（Binary Search），也叫折半查找，是一种高效的查找算法，专门用于在有序数组中快速定位目标元素。

二分查找的核心思想为每次都把查找范围缩小一半，直到找到目标，或确定目标不存在。

二分查找的前提条件如下：

（1）数组必须是有序的（升序或降序）。

（2）数组支持随机访问（比如 Python 列表、数组）。

注意：无序数组不能用二分查找！必须先排序

举一个例子：想象你在猜 1~100 的数字

（1）你先猜中间数 50；

（2）如果目标比 50 大，就直接排除 1~50，只看 51~100；

（3）再猜新范围的中间数，重复这个过程；

（4）最多 7 次就能找到答案。

这就是二分查找！每次砍掉一半范围。

假如你有一个有序数组 [2, 5, 8, 12, 15, 20, 25, 28, 30]，使用二分查找算法查找目标 25，过程如下：

第一步：

数组下标： 0   1   2    3    4    5    6    7    8
数组元素：[2,  5,  8,  12,  15,  20,  25,  28,  30]
          ↑                 ↑                   ↑
          |                 |                   |
      左边界 left        中间 mid           右边界 right
        (low=0)       (mid=4,值=15)          (high=8)

第一步：15 < 25 → 目标在右半区 → left = mid + 1 = 5

第二步：

下标：     0   1   2    3    4    5    6    7    8
元素：     [2,  5,  8,  12,  15, 20,  25,  28,  30]
                                 ↑    ↑         ↑
                                 |    |         |
                                left  mid      high
                                 (5)  (6)      (8)

第二步：25 == 25 → 找到！返回下标 6

示例代码：

def binary_search(arr, target):
    """二分查找算法实现，返回目标元素的索引，如果不存在则返回 -1"""
    # 左边界、右边界初始化
    left = 0
    right = len(arr) - 1

    while left <= right:
        # 计算中间索引（防止溢出写法：left + (right - left) // 2）
        mid = (left + right) // 2
        
        # 找到目标，返回索引
        if arr[mid] == target:
            return mid
        # 目标在右半部分
        elif arr[mid] < target:
            left = mid + 1
        # 目标在左半部分
        else:
            right = mid - 1

    # 循环结束没找到
    return -1


if __name__ == "__main__":
    # 有序数组
    nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
    # 目标元素
    target_num = 23

    # 二分查找
    result = binary_search(nums, target_num)
    if result != -1:
        print(f"元素 {target_num} 在数组中的索引为: {result}")
    else:
        print("元素不在数组中")

运行结果：

元素 23 在数组中的索引为: 5