寻找旋转排序数组中的最小值II（154）

题目

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4] 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7] 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例

输入：nums = [1,3,5] 输出：1

输入：nums = [2,2,2,0,1] 输出：0

提示

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

进阶

• 这道题是 寻找旋转排序数组中的最小值 (opens new window) 的延伸题目。
• 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

算法

二分查找

我们设旋转数组最后一项为nums[left]，设最小项为nums[min]，则有：

• nums[min]右侧的都小于等于nums[left]
• nums[min]左侧的都大于等于nums[left]

因为最小值肯定会出现在非连续递增的那一部分，所以我们使用二分查找判断开始结束范围的时候可以使用上面两个条件：

• 当nums[mid] > nums[end]时，因为nums[min]左侧都大于等于nums[end]，所以nums[min]出现在nums[mid]右侧，我们让start = mid + 1
• 当nums[mid] < nums[end]时，因为nums[min]右侧都小于等于nums[end]，所以nums[min]出现在nums[mid]左侧，我们让end = mid（因为最小值可能是nums[mid]，所以我们不减1）
• 当nums[mid] === nums[end]时，即使nums[end]是最小值，我们也有一个相同的nums[mid]，所以我们让end--
• 重复判断，最后结果就是nums[start]

const findMin = function (nums) {
	if (nums.length === 1 || nums[0] < nums[nums.length - 1]) return nums[0];
	let start = 0,
		end = nums.length - 1;
	while (start < end) {
		const mid = ~~((start + end) / 2);
		if (nums[end] > nums[mid]) {
			end = mid;
		} else if (nums[end] < nums[mid]) {
			start = mid + 1;
		} else {
			end--;
		}
	}
	return nums[start];
};