二分查找 解题模板

适用场景

有序数组中查找、值域二分答案、旋转数组

通用模板

标准二分

 
l, r = 0, len(nums)-1
 
while l <= r:
 
    mid = (l+r)//2
 
    if nums[mid] == target: return mid
 
    if nums[mid] < target: l = mid + 1
 
    else: r = mid - 1
 
return -1
 

左边界 / 右边界

 
# 第一个 >= target（左边界）
 
l, r = 0, len(nums)
 
while l < r:
 
    mid = (l+r)//2
 
    if nums[mid] >= target: r = mid
 
    else: l = mid + 1
 
return l  # l == len(nums) 表示不存在
 
# 最后一个 <= target（右边界）
 
l, r = -1, len(nums)-1
 
while l < r:
 
    mid = (l+r+1)//2  # 上取整
 
    if nums[mid] <= target: l = mid
 
    else: r = mid - 1
 
return l
 

旋转数组

 
# 判断哪半有序
 
if nums[l] <= nums[mid]:  # 左半有序
 
    if nums[l] <= target < nums[mid]: r = mid-1
 
    else: l = mid+1
 
else:  # 右半有序
 
    if nums[mid] < target <= nums[r]: l = mid+1
 
    else: r = mid-1
 

值域二分（二分答案）

 
l, r = min_val, max_val
 
while l < r:
 
    mid = (l+r)//2
 
    if count_less_equal(mid) >= k: r = mid
 
    else: l = mid + 1
 
return l
 

复杂度总结

模式	时间	空间	典型题
标准二分	O(log n)	O(1)	704
边界二分	O(log n)	O(1)	34、35
旋转数组	O(log n)	O(1)	33、153
值域二分	O(n log max)	O(1)	378、287

关键要点

• 开区间 vs 闭区间：while l < r vs while l <= r

• 避免整数溢出：mid = l + (r-l)//2

• 旋转数组判断有序的条件 nums[l] <= nums[mid] 注意等号（处理相同元素）

• 二分答案的关键是写对 count_less_equal 函数

→ 查看该分类题目：LeetCode学习路线图 > 八、二分查找

---

关联题型

关联题型	常见结合方式	典型题目
数组与哈希	有序数组 + 二分定位	33搜索旋转排序数组
排序	排序 + 二分加速	34搜索范围
二叉搜索树	BST 的二分性质	98验证BST, 230第K小