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

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。

请找出其中最小的元素。

示例

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

输入：nums = [4,5,6,7,0,1,2] 输出：0

输入：nums = [1] 输出：1

提示

• 1 <= nums.length <= 5000
• -5000 <= nums[i] <= 5000
• nums 中的所有整数都是 唯一 的
• nums 原来是一个升序排序的数组，但在预先未知的某个点上进行了旋转

算法

二分搜索

当一个排序数组被旋转后，一定有一个旋转点transPoint满足nums[transPoint] < nums[transPoint]：

• 在这个旋转点transPoint左边都是比nums[0]大的值
• 在这个旋转点transPoint右边都是比nums[0]小的值

我们将这个数组一分为二，令中点是mid，那么切分后的数组一部分必定是排序的，另一部分可能是不排序的（因为旋转点是数组第一项时，旋转后的数组还是排序的）

我们比较中点nums[mid]和nums[0]的值（当旋转后数组不排序时）：

• 如果nums[mid]>nums[0]，那么说明中点左侧是排序的，旋转点transPoint在中点右侧
• 如果nums[mid]<nums[0]，那么说明中点右侧是排序的，旋转点transPoint在中点左侧

所以我们可以通过二分查找，一步步缩小搜索范围，找到这个transPoint：

• 先排除特殊情况，当数组只有一项或数组是排序的（即nums[0]<nums[nums.length-1]）情况，根据题意返回nums[0]
• 找到中点mid，判断中点nums[mid]或nums[mid+1]是否是旋转点，如果是则返回旋转点
• 如果没有找到旋转点，那么根据上面的关于nums[0]和nums[mid]的判断情况，收缩搜索范围，继续查找

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