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

34. 在排序数组中查找元素的第一个和最后一个位置​1为什么要二分两次数组有序二分能在log n时间定位“边界”。我们想要的是lefttarget 第一次出现的位置最左righttarget 最后一次出现的位置最右2lower_bound 是什么lower_bound(x)返回第一个 x 的下标。比如nums [5,7,7,8,8,10]lower_bound(8) 3第一个 8 的位置就是 8 的第一个出现lower_bound(9) 5第一个 9 的位置是 103怎么得到右边界右边界 最后一个target的位置。如果我们能找到lower_bound(target 1)它是第一个 target1的位置那它前一个位置-1一定是最后一个 target如果 target 存在所以right lower_bound(target 1) - 14为什么要检查存在性有可能数组里根本没有 target。例如 nums[1,2,4], target3left lower_bound(3)会得到 2指向 4但nums[left] ! target说明没找到返回[-1,-1]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 # 第一个 target1 的位置再往左一步就是最后一个 target # 验证 target 是否真的存在 if left len(nums) or nums[left] ! target: return [-1, -1] return [left, right]162.寻找峰值​把数组看成一座“山路”每个数字是高度。你站在中间mid只看右边一格如果nums[mid] nums[mid1]说明右边更高你正走在“上坡” 山顶一定在右边继续往右找否则nums[mid] nums[mid1]说明右边更低你在“下坡或山顶附近” 山顶一定在左边包含 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 l153. 寻找旋转排序数组中的最小值​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实际上不会达到这里因为按照题意我们总能在循环里找到最小值。