当前位置：首页 > news >正文

每天五分钟：二分查找-LeetCode高频题解析_day4

news 2026/3/27 3:56:20

34. 在排序数组中查找元素的第一个和最后一个位置

from typing import List class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: # 找到第一个 >= target 的位置（左边界） def lower_bound(x: int) -> int: l, r = 0, len(nums) # 注意：右边用 len(nums)，表示“开区间” while l < r: mid = (l + r) // 2 if nums[mid] < x: l = mid + 1 else: r = mid return l left = lower_bound(target) # 第一个 >= target 的位置 right = lower_bound(target + 1) - 1 # 第一个 >= target+1 的位置，再往左一步就是最后一个 target # 验证 target 是否真的存在 if left == len(nums) or nums[left] != target: return [-1, -1] return [left, right]

162.寻找峰值

把数组看成一座“山路”，每个数字是高度。

你站在中间mid，只看右边一格：

如果nums[mid] < nums[mid+1]：说明右边更高，你正走在“上坡”
👉 山顶一定在右边（继续往右找）
否则nums[mid] > nums[mid+1]：说明右边更低，你在“下坡或山顶附近”
👉 山顶一定在左边（包含 mid）（继续往左找）

这就是二分的依据：只看坡度方向，就能保证峰值在那一侧。

class Solution: def findPeakElement(self, nums) -> int: l, r = 0, len(nums) - 1 while l < r: mid = (l + r) // 2 if nums[mid] < nums[mid + 1]: # 右边更高：峰值在右侧 l = mid + 1 else: # 右边更低或持平：峰值在左侧（含 mid） r = mid return l

153. 寻找旋转排序数组中的最小值

class Solution: def findMin(self, nums): left = 0 right = len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[left] <= nums[mid]: # 左侧有序 if nums[mid] <= nums[right]: # 整个数组有序 return nums[left] else: # 左有序右无序 left = mid + 1 else: # 左侧无序 if nums[mid] <= nums[right]: # 左无序右有序 right = mid else: # 理论上不会出现这个else块，因为正常情况下 # 左右两侧必有一侧为有序 pass return -1

# 解释：
# 初始化指针：
# left 和 right 分别初始化为数组的左端和右端。
# 循环进行二分搜索：
# 计算当前中间位置的索引 mid。
# 判断左半部分是否有序：if nums[left] <= nums[mid]。

# 如果左半部分有序，再进一步判断整个数组是否有序：if nums[mid] <= nums[right]。

# 如果是，则返回左端的值，nums[left]。
# 否则，说明右半部分存在无序部分，所以将 left 更新为 mid + 1。
# 如果左半部分无序，则进一步判断右半部分是否有序：if nums[mid] <= nums[right]。

# 如果是，将 right 更新为 mid，因为最小值在左侧部分。
# 根据题意，不会进入到else块，因为存在旋转的情况下，左右两部分总有一部分是有序的。
# 返回结果：
# 如果在循环中找到了最小值，则返回最小值。
# 否则返回 -1（实际上不会达到这里，因为按照题意我们总能在循环里找到最小值）。