classSolution:deffindMin(self,nums: List[int]) ->int: n =len(nums) left, right =0, n -1while left < right: mid = left + (right - left) //2# 为何不用nums[mid] >= nums[left] 判断mid是否在左分支?# 因为存在重复,仅仅该条件不足以说明if nums[mid]> nums[right]:#mid在左分支,则左边界右移 left = mid +1elif nums[mid]< nums[left]:#mid在右分支,则右边界左移 right = mid # 右边界移的慢一些(因为要找右断点)else:# 不确定在哪个分支,缩小右边界(因为要找右断点) right -=1#循环结束left就是右断点return nums[left]
扩展:若是求旋转数组最大值?
解法一求的是断点中的右断点(断开处有两点,升序的话左断点较大,右断点较小)
求最大值即求左断点,将上面代码反过来写即可:
classSolution:deffindMin(self,nums) ->int: n =len(nums) left, right =0, n -1while left < right: mid = left + (right - left) //2if nums[mid]> nums[right]: left = midelif nums[mid]< nums[left]: right = mid -1else: left +=1return nums[right]