二分查找
Binary Search
本机进度仅保存在当前浏览器
题目描述
给定一个 n 个元素升序排列的整数数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，存在则返回下标，否则返回 -1。
示例：nums = [-1, 0, 3, 5, 9, 12]，target = 9，输出 4。
解题思路
- 二分的骨架：在闭区间 [l, r] 内，取中点与目标比较，每次淘汰一半。
- nums[mid] < target 说明答案只可能在右半段，l = mid + 1；反之 r = mid - 1。
- 循环条件 l <= r 对应闭区间语义；区间语义（闭/左闭右开）一旦选定，边界增减必须成套，这是二分出 bug 的主要来源。
- 中点用 l + (r - l) // 2 计算可避免大数相加溢出（其他语言中尤其重要）。
参考实现
查看参考实现Python · 建议先自行作答
def search(nums, target):
# 闭区间 [l, r] 标准二分
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r - l) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
l = mid + 1
else:
r = mid - 1
return -1