Find Minimum in Rotated Sorted Array

    (i.e., might become 4 5 6 7 0 1 2).

    Find the minimum element.

    Example

    Note

    You may assume no duplicate exists in the array.

    题解

    如前节所述，对于旋转数组的分析可使用画图的方法，如下图所示，升序数组经旋转后可能为如下两种形式。

    最小值可能在上图中的两种位置出现，如果仍然使用数组首部元素作为target去比较，则需要考虑图中右侧情况。使用逆向思维分析，如果使用数组尾部元素分析，则无需图中右侧的特殊情况。不过考虑在内的话也算是一种优化。

    1.     /**
    2.      * @param num: a rotated sorted array
    3.      * @return: the minimum number in the array
    4.      */
    5.     public int findMin(int[] num) {
    8.         int lb = 0, ub = num.length - 1;
    9.         // case1: num[0] < num[num.length - 1]
    10.         // if (num[lb] < num[ub]) return num[lb];
    12.         while (lb + 1 < ub) {
    13.             int mid = lb + (ub - lb) / 2;
    14.             if (num[mid] < num[ub]) {
    16.             } else {
    17.                 lb = mid;
    18.             }
    19.         }
    21.         return Math.min(num[lb], num[ub]);
    22.     }

    仅需注意使用num[end](使用 num[lb]不是那么直观)作为判断依据即可，由于题中已给无重复数组的条件，故无需处理特殊条件。