跳到主要内容

旋转排序数组中的最小值(153)

题目描述

找出在旋转排序数组中的最小值,本题中数组不存在重复值

样例

Input: [3,4,5,1,2]
Output: 1

Input: [4,5,6,7,0,1,2]
Output: 0

题解

左闭右开,寻找最小值。由于最小值一定是靠右的,所以我们应该使用左闭右开靠右的写法。

关键点在于确定mid 是落在哪一段?

这里一定要比较 num[mid] 和 num[right]。因为比较left的话,是无法区别最小值是在左边还是右边,下面就是例子。

image-20201125210852014

这样我们的判断条件就有了

  • nums[mid] < nums[right]:right = mid
  • nums[mid] >= nums[right]:left = mid + 1

解题上,可以有两种思路去实现:

第一种,是寻找最小值,即靠右的二分查找

第二种,是寻找最大值,即靠左的二分查找。返回 nums[(pos + 1) % len(nums)]

Python示例

# 寻找最小值
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) >> 1
if nums[mid] < nums[right]: # mid 有可能是最小值,不拒绝
right = mid
else:
left = mid + 1
return nums[left]

# 寻找最大值
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2 + 1
if nums[mid] > nums[left]: # mid 有可能是最大值,不拒绝
left = mid
else:
right = mid - 1
return nums[(left + 1) % len(nums)]

Go 示例

func findMin(nums []int) int {
if len(nums) == 1 {
return nums[0]
}

n := len(nums)
if nums[0] < nums[n - 1] { // 有序
return nums[0]
}
i, j:= 0, n - 1
for i < j{
mid := (i + j) >> 1
if nums[mid] < nums[j] {
j = mid
} else {
i = mid + 1
}
}
return nums[i]
}