本文目录导读：
我来给你介绍Python二分查找的精准实现方法,包括基础版本和多种实用案例。
基础二分查找（精准查找）
标准实现
def binary_search(arr, target):
"""
精准二分查找，返回目标值的索引
如果不存在，返回-1
"""
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 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, 13, 15]
print(binary_search(arr, 7)) # 输出: 3
print(binary_search(arr, 8)) # 输出: -1
查找边界值（精准定位）
查找第一个等于target的位置
def find_first_equal(arr, target):
"""查找第一个等于target的元素索引"""
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = left + (right - left) // 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]
print(find_first_equal(arr, 2)) # 输出: 1
查找最后一个等于target的位置
def find_last_equal(arr, target):
"""查找最后一个等于target的元素索引"""
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
result = mid # 记录当前位置
left = mid + 1 # 继续向右查找
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
# 测试
arr = [1, 2, 2, 2, 3, 4, 5]
print(find_last_equal(arr, 2)) # 输出: 3
查找近似值（最接近目标）
查找最接近target的元素
def find_closest(arr, target):
"""查找最接近target的元素索引"""
if not arr:
return -1
left, right = 0, len(arr) - 1
# 边界情况处理
if target <= arr[left]:
return left
if target >= arr[right]:
return right
while left < right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
left = mid + 1
else:
right = mid - 1
# 比较两个最接近的元素
if abs(arr[left] - target) <= abs(arr[left + 1] - target):
return left
else:
return left + 1
# 测试
arr = [1, 3, 5, 7, 9, 11]
print(find_closest(arr, 6)) # 输出: 2 (值5)
print(find_closest(arr, 8)) # 输出: 3 (值7)
实际应用案例
案例1：查找插入位置
def search_insert(nums, target):
"""
LeetCode 35: 搜索插入位置
返回target应该插入的索引位置
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
# 测试
nums = [1, 3, 5, 6]
print(search_insert(nums, 5)) # 输出: 2
print(search_insert(nums, 2)) # 输出: 1
print(search_insert(nums, 7)) # 输出: 4
案例2：旋转数组查找
def search_rotated(nums, target):
"""
LeetCode 33: 搜索旋转排序数组
"""
if not nums:
return -1
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
# 判断哪部分是有序的
if nums[left] <= nums[mid]: # 左半部分有序
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else: # 右半部分有序
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
# 测试
nums = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(nums, 0)) # 输出: 4
print(search_rotated(nums, 3)) # 输出: -1
案例3：求平方根
def my_sqrt(x):
"""
LeetCode 69: x的平方根
返回整数部分
"""
if x == 0 or x == 1:
return x
left, right = 1, x
while left <= right:
mid = left + (right - left) // 2
if mid * mid == x:
return mid
elif mid * mid < x:
left = mid + 1
else:
right = mid - 1
return right
# 测试
print(my_sqrt(8)) # 输出: 2
print(my_sqrt(16)) # 输出: 4
性能优化版本
使用bisect模块（Python内置）
import bisect
# bisect_left: 查找第一个大于等于target的位置
# bisect_right: 查找第一个大于target的位置
arr = [1, 2, 2, 2, 3, 4, 5]
# 查找等于target的范围
left_idx = bisect.bisect_left(arr, 2) # 第一个2的位置
right_idx = bisect.bisect_right(arr, 2) # 最后一个2的下一个位置
print(f"2的范围: [{left_idx}, {right_idx-1}]") # 输出: [1, 3]
通用二分查找模板
def binary_search_template(nums, target):
"""
通用二分查找模板
"""
left, right = 0, len(nums) - 1
while left + 1 < right: # 当区间长度>2时
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid
else:
right = mid
# 最后检查两个元素
if nums[left] == target:
return left
if nums[right] == target:
return right
return -1
# 测试
arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search_template(arr, 7)) # 输出: 3
注意事项
- 边界条件：确保left <= right正确使用
- 中点计算：使用
left + (right - left) // 2避免整数溢出 - 循环终止：确保最终能退出循环
- 数组有序：二分查找要求数组有序
- 重复元素：注意处理重复元素的情况
这些案例覆盖了大多数二分查找的应用场景,可以根据具体需求选择合适的实现方式。
