力扣数组
704.二分查找
704.二分查找
https://leetcode.cn/problems/binary-search
题目
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4 示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1 提示：
- 你可以假设 nums 中的所有元素是不重复的。
- n 将在 [1, 10000]之间。
- nums 的每个元素都将在 [-9999, 9999]之间。
思路
- 定义查找区间
[left, right]（初始为整个数组）； - 计算区间中间位置
midx，比较nums[midx]与目标值target； - 根据比较结果缩小区间：
- 若
nums[midx] == target：找到目标，返回mid； - 若
nums[midx] > target：目标在左半区间，调整右边界right = midx - 1； - 若
nums[midx] < target：目标在右半区间，调整左边界left = midx + 1；
- 若
- 重复步骤 2-3，直到区间无效（
left > right），说明目标不存在，返回 - 1。
解法
nums = [-1, 0, 3, 5, 9, 12]
target = 9
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
midx = left + (right - left) // 2
if nums[midx] < target:
left = midx + 1
elif nums[midx] > target:
right = midx - 1
else:
return midx
return -1解释
| 代码片段 | 作用与原因 |
|---|---|
right = len(nums)-1 | 闭区间 [0, len-1] 覆盖整个数组，符合 “左闭右闭” 的定义 |
while left <= right | 当 left == right 时，区间还有最后一个元素需要检查（如数组只有 1 个元素） |
mid = left + (right-left)//2 | 等价于(left+right)/2, 但避免 left+right 整数溢出，且 // 是向下取整（保证 mid 是整数下标） |
right = midx - 1 | 因为 nums[midx] > target，midx 本身已排除，右边界需左移一位 |
left = midx + 1 | 因为 nums[midx] < target，midx 本身已排除，左边界需右移一位 |
进阶
如果数组有重复元素，基础版只能找到任意一个匹配项，如何找「第一个出现的位置」或「最后一个出现的位置」？