今�Hの国の呵呵君: [Algorithm]Find Minimum in Rotated Sorted Array(sorted as from max to min)

今�Hの国の呵呵君: [Algorithm]Find Minimum in Rotated Sorted Array(sorted as from max to min)

[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

Read full article from 今�Hの国の呵呵君: [Algorithm]Find Minimum in Rotated Sorted Array(sorted as from max to min)