一句话总结
二分查找核心是区间定义：左闭右闭 [left, right] 用 left <= right，左闭右开 [left, right) 用 left < right。查找左边界：找到 target 后收缩右边界；查找右边界：找到 target 后收缩左边界。旋转数组二分：比较 nums[mid] 和 nums[left]/nums[right] 判断有序区间。时间复杂度 O(log n)，空间 O(1)。
初级理解
标准二分查找
# 左闭右闭 [left, right]
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right: # left <= right，因为 left==right 时区间有效
mid = left + (right - left) // 2 # 防止溢出
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1 # target 在右半区
else:
right = mid - 1 # target 在左半区
return -1
# 左闭右开 [left, right)
def binary_search2(nums, target):
left, right = 0, len(nums)
while left < right: # left < right，因为 left==right 时区间为空
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid # 右开，所以 right = mid
return -1
一句话总结：二分查找关键是区间定义，左闭右闭用 <=，左闭右开用 <。
中级深入
查找左边界（第一个等于 target 的位置）
# 查找左边界
def search_left(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid - 1 # 找到 target 也继续向左收缩
else:
left = mid + 1
# left 是第一个 >= target 的位置
if left < len(nums) and nums[left] == target:
return left
return -1
# 示例
nums = [1, 2, 2, 2, 3, 4]
search_left(nums, 2) # 返回 1（第一个 2 的位置）
查找右边界（最后一个等于 target 的位置）
# 查找右边界
def search_right(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] <= target:
left = mid + 1 # 找到 target 也继续向右收缩
else:
right = mid - 1
# right 是最后一个 <= target 的位置
if right >= 0 and nums[right] == target:
return right
return -1
# 示例
nums = [1, 2, 2, 2, 3, 4]
search_right(nums, 2) # 返回 3（最后一个 2 的位置）
中级要点：左边界找到 target 收缩 right，右边界找到 target 收缩 left。
高级拓展
旋转数组二分查找
# 搜索旋转排序数组（无重复）
def search_rotate(nums, target):
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 # target 在左半区
else:
left = mid + 1 # target 在右半区
else: # 右半区有序
if nums[mid] < target <= nums[right]:
left = mid + 1 # target 在右半区
else:
right = mid - 1 # target 在左半区
return -1
# 示例
nums = [4, 5, 6, 7, 0, 1, 2]
search_rotate(nums, 0) # 返回 4
寻找旋转数组最小值
# 寻找旋转排序数组最小值
def find_min(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
left = mid + 1 # 最小值在右半区
else:
right = mid # 最小值在左半区（包括 mid）
return nums[left]
# 示例
nums = [4, 5, 6, 7, 0, 1, 2]
find_min(nums) # 返回 0
实战场景
场景：在排序数组中查找元素的第一个和最后一个位置（LeetCode 34）
def search_range(nums, target):
def find_left():
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid - 1
else:
left = mid + 1
return left
def find_right():
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
return right
l = find_left()
r = find_right()
if l <= r:
return [l, r]
return [-1, -1]
面试模拟
面试官：二分查找的边界条件怎么处理？
你：关键是统一区间定义。左闭右闭 [left, right] 用 left <= right，更新时 left=mid+1, right=mid-1；左闭右开 [left, right) 用 left < right，更新时 left=mid+1, right=mid。mid 计算用 left+(right-left)//2 防止溢出。
面试官：旋转数组怎么二分？
你：比较 nums[mid] 和 nums[left]（或 nums[right]）判断哪边有序。如果 nums[left] <= nums[mid]，左半区有序，判断 target 是否在左半区范围内；否则右半区有序。注意有重复元素时，nums[left]==nums[mid]==nums[right] 无法判断，需要 left++ 或 right-- 缩小范围。