34 | 理论讲解：二分查找-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

### 第34讲 理论讲解：二分查找

#### 引言

在计算机科学领域，算法是解决问题的核心工具，而二分查找（Binary Search）作为搜索算法中的佼佼者，凭借其高效的性能在各类面试和实际应用中大放异彩。本讲将深入剖析二分查找算法的理论基础、实现细节、变体应用以及性能分析，帮助读者彻底掌握这一经典算法，为算法面试及实际编程打下坚实基础。

#### 一、二分查找的基本概念

**定义**：二分查找算法是一种在有序数组中查找特定元素的搜索算法。它通过不断将数组分成两半，判断目标值可能与哪一半的子数组中的元素相等，然后继续在相应的子数组中查找，直到找到目标值或确定目标值不存在于数组中。

**前提条件**：二分查找要求数组必须是有序的，无论是升序还是降序，因为有序性是二分查找能够高效运作的基础。

**适用场景**：当数据量较大且数据已排序时，二分查找能够显著减少查找时间，其时间复杂度为O(log n)，远优于线性查找的O(n)时间复杂度。

#### 二、二分查找的基本实现

**递归实现**：

递归实现的二分查找通过不断调用自身函数，每次都将搜索范围缩小一半。以下是一个简单的升序数组二分查找的递归实现示例（Python）：

```python
def binary_search_recursive(arr, left, right, target):
    if left > right:
        return -1  # 表示未找到
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # 找到目标，返回索引
    elif arr[mid] < target:
        return binary_search_recursive(arr, mid + 1, right, target)  # 在右半部分查找
    else:
        return binary_search_recursive(arr, left, mid - 1, target)  # 在左半部分查找

# 调用示例
arr = [1, 3, 5, 7, 9, 11]
target = 7
result = binary_search_recursive(arr, 0, len(arr) - 1, target)
print(result)  # 输出：3
```

**迭代实现**：

迭代版本的二分查找通过循环来实现，同样是将数组不断二分，直到找到目标值或搜索范围为空。

```python
def binary_search_iterative(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  # 未找到目标

# 调用示例
arr = [1, 3, 5, 7, 9, 11]
target = 7
result = binary_search_iterative(arr, target)
print(result)  # 输出：3
```

#### 三、二分查找的变体

**1. 查找第一个等于给定值的元素**：

在某些情况下，我们不仅需要知道目标值是否存在，还需要知道它第一次出现的位置。这需要对二分查找进行微调，确保在找到目标值时，搜索范围继续向左缩小，直到找到最左边的目标值。

**2. 查找最后一个等于给定值的元素**：

类似地，我们可能也需要找到目标值最后一次出现的位置。这要求我们在找到目标值后，将搜索范围向右缩小，直到无法再找到目标值为止。

**3. 旋转有序数组中的查找**：

对于一个被旋转的有序数组（如[4, 5, 6, 7, 0, 1, 2]），二分查找仍然可以应用，但需要在每次迭代中根据当前中间值与数组首尾元素的关系，动态调整搜索范围。

#### 四、二分查找的性能分析

**时间复杂度**：二分查找的时间复杂度为O(log n)，其中n是数组的长度。这是因为每次迭代都将搜索范围减半，直至找到目标值或搜索范围为空。

**空间复杂度**：对于递归实现，空间复杂度主要取决于递归的深度，最坏情况下为O(log n)（即递归栈的深度）。而对于迭代实现，空间复杂度为O(1)，因为它只使用了常量级别的额外空间。

#### 五、二分查找的注意事项

1. **数组必须有序**：二分查找的前提是数组有序，因此在应用前需确保数组已排序。
2. **整数溢出问题**：在计算中间索引`(left + right) // 2`时，应避免直接相加导致的整数溢出，可改为`left + (right - left) // 2`。
3. **边界条件处理**：在迭代或递归过程中，需仔细处理边界条件，如`left`和`right`的关系，以及找到目标值后的返回逻辑。
4. **数据类型考虑**：二分查找不仅适用于整数数组，也适用于其他类型的有序数组，但需注意比较操作符的适用性。

#### 六、总结

二分查找是一种高效且经典的搜索算法，其核心思想是通过不断缩小搜索范围来快速定位目标值。本讲从二分查找的基本概念出发，详细讲解了其基本实现（递归与迭代）、变体应用以及性能分析，并强调了实际应用中需要注意的几点事项。掌握二分查找不仅有助于提升算法面试的表现，也是解决实际问题中优化搜索效率的重要手段。希望读者通过本讲的学习，能够深刻理解并灵活运用二分查找算法。

该分类下的相关小册推荐：

编程之道-算法面试(下)

数据结构与算法(上)

数据结构与算法(中)

编程之道-算法面试(上)

数据结构与算法(下)

数据结构与算法之美

业务开发实用算法精讲