从零学算法154

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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须尽可能减少整个过程的操作步骤。
示例 1：
输入：nums = [1,3,5]
输出：1
示例 2：
输入：nums = [2,2,2,0,1]
输出：0

• 暴力解法就不过多赘述了，从头到尾遍历一遍看哪个值突然不是保持升序的，那他就是最小值，或者直接对数组排序然后取首个元素，没意义。
• 他人解法：首先经过旋转后以最小值 x 为分界点会分为左右两个升序数组，并且 x 一定在右数组，且为起点，因为旋转就是把最小值转到右边去了（旋转 0 次可以视为只有右数组）。从左右两端 left，right 为区间进行查找，中点值 mid 的可能性有三种：
  • mid < right: 说明 mid 在右数组，所以 mid 可能为 x，所以直接排除区间 (mid,right]，即 right 更新为 mid
  • mid > right: 说明 mid 在左数组，在左数组 mid 就不可能为 x 了，所以所以直接排除区间 [left,mid]，即 更新 left 为 mid+1
  • mid = right: 此时由于数组元素可能重复比如 [2,2,2,0,2] 和 [2,0,2,2,2]，此时无法确定 mid 在左右哪个数组，不能直接去掉一部分区间了。但是无论是哪种情况，right 肯定是没用了，因为就算 right 等于 x，那我 mid 也等于 x，所以就谨慎地只去掉 right，也就是 right = right - 1。
  • 当 mid = right 时。换个说法再解释一下：首先如果 x 小于 right 对应的值，那 right 去掉也就去掉了，x 仍然在 [left，right-1]；其次就算 right 对应的就是 x，首先 mid <= left ，因为 mid=right=x，x 已经是最小值了，那最小值肯定小于等于 left 了，同时 left<=mid<right 是恒成立的（因为 mid 是 (left+right)/2），但是你这时候 mid=right=x，也就是说 left<=mid<x，mid < x 代表了 mid 在左数组（因为 x 是右数组起点），既然 mid 在左数组，那么根据左数组的升序特性 left<=mid 恒成立。mid <= left 并且 mid >= left，那就只能说 mid 岂不是就等于 left，由于区间 [left,mid] 是升序的，那么 left - mid 的值都是相等的。在 right 对应 x 时减 1 后代表的其实就是正好把右数组全部抛弃了，剩下的左数组全等，且都等于 x，那么无论你怎么查找，最后剩下的值都等于我们最终要的 x。
• 为什么 mid 不和 left 比较，因为二分的目的是为了判断 mid 处于左右的哪个数组。mid > left 时比如 [1,2,3,4,5] 和 [3,4,5,1,2] mid 分别在右数组和左数组，这就无法判断了。

•   public int minArray(int[] nums) {int i = 0,j = nums.length - 1;while(i<j){int mid = (i + j)/2;if(nums[mid] > nums[j])i=mid+1;else if(nums[mid] < nums[j])j=mid;else j--;}return nums[i];}