二分查找
二分查找是一种高效的搜索算法，要求数据已经有序排列。
概述
二分查找通过不断将搜索范围减半来定位目标元素。
算法步骤
- 初始化指针: 设置左指针和右指针
- 计算中间位置: mid = (left + right) // 2
- 比较中间元素:
- 如果中间元素等于目标，返回索引
- 如果中间元素小于目标，搜索右半部分
- 如果中间元素大于目标，搜索左半部分
- 重复: 直到找到目标或搜索范围为空
实现
python
def binary_search(arr, target):
left = 0
right = 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 = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
result = binary_search(arr, target)
print(f"元素 {target} 在索引 {result} 处") # 元素 23 在索引 5 处递归版本
python
def binary_search_recursive(arr, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
# 示例
result = binary_search_recursive(arr, target, 0, len(arr) - 1)
print(f"元素 {target} 在索引 {result} 处") # 元素 23 在索引 5 处复杂度分析
| 情况 | 时间复杂度 |
|---|---|
| 平均 | O(log n) |
| 最好 | O(1) |
| 最坏 | O(log n) |
空间复杂度
- 迭代版本：O(1)
- 递归版本：O(log n)
变体
查找第一个出现的位置
python
def binary_search_first(arr, target):
left = 0
right = len(arr) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
result = mid
right = mid - 1 # 继续向左搜索
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
# 示例
arr = [1, 2, 2, 2, 3, 4, 5]
target = 2
result = binary_search_first(arr, target)
print(f"元素 {target} 第一次出现在索引 {result} 处") # 元素 2 第一次出现在索引 1 处查找最后一个出现的位置
python
def binary_search_last(arr, target):
left = 0
right = len(arr) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
result = mid
left = mid + 1 # 继续向右搜索
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
# 示例
result = binary_search_last(arr, target)
print(f"元素 {target} 最后一次出现在索引 {result} 处") # 元素 2 最后一次出现在索引 3 处查找插入位置
python
def binary_search_insert(arr, target):
left = 0
right = len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left
# 示例
arr = [1, 3, 5, 7]
target = 4
result = binary_search_insert(arr, target)
print(f"元素 {target} 应插入到索引 {result} 处") # 元素 4 应插入到索引 2 处应用场景
- 有序数组的快速查找
- 数据库索引查找
- 二分查找树的查找
注意事项
- 数组必须有序: 二分查找依赖有序数组
- 整数溢出: 在计算 mid 时要注意溢出问题
- 边界条件: 注意处理边界情况