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

问题153 寻找旋转排序数组中的最小值 ★★☆☆☆

https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/

这个题目和问题33几乎一样，问题33是查找特定值，问题153是查找最小值，都是基于rotation破坏有序性做文章。在问题33的经验之上，我们可以很容易判断mid节点是在左侧上升段还是右侧上升段。不过问题153还有一点不同，就是可能rotation后还是全部有序的。正因为这一点，比较nums[mid]和nums[left]的大小关系不足以确认最小值在左侧还是右侧。比如，nums[mid] > nums[left]，如果是问题33的背景下，那么mid节点一定是在左侧上升段，即最小值在右侧。但是，由于问题153可能rotation后和原数组一样，那么此时，同样nums[mid] > nums[left]，但是最小值在左侧。因此，和nums[left]比较没有用。相反的，nums[mid]和nums[right]的大小关系就可以确认最小值在左侧还是右侧： nums[mid] > nums[right]，最小值在右侧，nums[mid]不会是最小值，left=mid+1后继续； nums[mid] < nums[right]，最小值在左侧，nums[mid]可能是最小值，right=mid后继续。

	public int findMin(int[] nums) {
		int left = 0, right = nums.length - 1;
		while (left < right) {
			int mid = left + (right - left) / 2;
			if (nums[mid] > nums[right]) {
				left = mid + 1;
			} else if (nums[mid] < nums[right]) {
				right = mid;
			}
		}

		return nums[left];
	}

在 LeetCode 查看