[Algorithm]Find Minimum in Rotated Sorted Array(sorted as from max to min)

在原题Find Minimum in Rotated Sorted Array中，array的顺序是从小到大的。这次我们把array的顺序改成从大到小，解法会发生什么变化吗？通过这一题，我们会总结二分法边界条件的相关问题。

这一题的分析思路是和原题是一样的，同样为了代码的简洁我们比较A[lo]和A[mid]：

• 如果A[mid] < A[lo]，那么[lo, mid]是sorted的，minimum只可能在[mid, hi]区间里。
• 如果A[mid] < A[lo]，那么[mid, hi]不是sorted的，minimum只可能在[lo, mid)区间里。

所以如果A[mid] < A[lo]，我们更新lo = mid；如果A[mid] < A[lo] 我们更新hi = mid - 1。但是随之而来的问题就是和原题不同，当我们把lo复制为mid的时候，当hi == lo  + 1的时候，二分就无法向下进行了，因为mid会一直等于lo。所以这个时候当hi <= lo + 1的时候我们就应该跳出，然后找lo和hi中较小的那一个。

分析到这里，我们可以看出，当二分的策略不同的时候，边界条件也是不同的，具体总结如下：

• [lo, hi] -> [lo, mid) + (mid, hi]，这个时候每次更新的时候lo = mid + 1，hi = mid - 1，跳出的条件至少应该是lo > hi
• [lo, hi] -> [lo, mid] + (mid, hi]，这个时候每次更新的时候lo = mid + 1，hi = mid，跳出的条件至少应该是lo >= hi，若条件为lo >= hi，跳出的时候情况为lo == hi
• [lo, hi] -> [lo, mid) + [mid, hi]，这个时候每次更新的时候lo = mid，hi = mid - 1，跳出的条件至少应该是lo + 1 >= hi，若条件为lo  + 1  >= hi，跳出的时候情况为lo == hi 或者 lo + 1 == hi
• [lo, hi] -> [lo, mid) + (mid, hi]，这个时候每次更新的时候lo = mid，hi = mid，跳出的条件至少应该是lo + 1 >= hi，若条件为lo  + 1  >= hi，跳出的时候情况为 lo + 1 == hi

本题代码如下：

	public class Solution {
	public int findMin(int[] num) {
	if (num == null)
	return -1;
	int len = num.length;
	int lo = 0, hi = len - 1;
	while (hi - lo > 1) {
	int mid = lo + (hi - lo) / 2;
	if (num[mid] < num[lo])
	lo = mid;
	else
	hi = mid - 1;
	}
	return num[lo] <= num[hi]? num[lo]: num[hi];
	}
	}

view raw find minimum in sorted array follow up.java hosted with ❤ by GitHub