局部最小值
题目:给定一个数组,每两个相邻的数组不等,找到该数组上任意一个局部最小值。
定义:nums[1] > nums[0]
nums[len(nums) - 2] > nums[len(nums) - 1]
nums[n-1] > nums[n] && nums[n] < nums[n+1]
题目解析
通过上面的定义已知三种情况
- 第一个数小于第二个数
- 最后一个数小于倒数第二个数
3.左右两边的数都比中间这个数大
第一种和第二种很好判断,关键在于第三种情况。如果出现第三种情况说明不符合第一种和第二种情况。也就是说nums[1] < nums[0] 和nums[n-1] < nums[n] && nums[n] > nums[n+1].
第一个数比第二个数大,说明他是向下的趋势。最后一个比倒数第二个大,说明是向上的趋势。那么先向下再向上必然存在局部最小值。
画图解析:
必然存在局部最小值。
# 求局部最小值
def part_most_min(nums):if nums is None or len(nums) == 0:return -1if len(nums) == 1:return 0# 检查左边界if nums[0] < nums[1]:return 0# 检查右边界if nums[-1] < nums[-2]:return len(nums) - 1left, right = 1, len(nums) - 2while left <= right:mid = left + (right - left) // 2# 如果中间元素比两边都小,就是局部最小值if nums[mid] < nums[mid - 1] and nums[mid] < nums[mid + 1]:return mid# 如果中间元素比左边大,局部最小值在左边elif nums[mid] > nums[mid - 1]:right = mid - 1# 如果中间元素比右边大,局部最小值在右边else:left = mid + 1return left