/**
 * Suppose a sorted array is rotated at some pivot unknown to you beforehand.
 * (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
 * 
 * Find the minimum element.
 * You may assume no duplicate exists in the array.
 * 
 * Tags: Array, Binary Search
 */
class FindRotatedArrMin {
    public static void main(String[] args) {
        int[] num = { 3, 4, 5, 6, 0, 1, 2 };
        // int[] num = { 4, 5, 6, 7, 0, 1, 2 };
        System.out.println(findMin(num));
    }
    
    static int findMin(int[] num) {
        int l = 0;
        int r = num.length - 1;
        if (num.length == 1 || num[l] < num[r]) return num[0];
        
        int mid = 0;
        
        /* There's n-1 pairs of adjacent nodes.
         * Rotation brings one pair with reverse order.
         * If the original sequence is in ascending order, the special one is max-min.
         * Any range [left,right] contains this pair must satisify num[left] > num[right].
         * num[right] < num[0] < num[left].
         * Try to capture this range with Binary Search.
         */        
        while (l < r) {
            mid = l + (r - l) / 2;
            if(num[l] > num[mid]) r = mid;
            else l = mid; //no dups. no "="
            //System.out.println(mid);
            //if (num[l] < num[mid]) l = mid;
            //else r = mid;
        }
        return num[l + 1]; //l:max, r:min
    }
    
}
@@ -949,16 +949,20 @@
        *
+ So,
  num%5Brig
@@ -983,24 +983,117 @@
  num%5Bleft%5D.%0A
+         * Meanwhile, if num%5Bleft%5D %3E num%5Bright%5D, we have max-min within %5Bleft, right%5D range.%0A
          * T
@@ -1228,16 +1228,18 @@
         
+//
 if(num%5Bl
@@ -1273,16 +1273,18 @@
         
+//
 else l =
@@ -1306,16 +1306,35 @@
 . no %22=%22
+, num%5Bl%5D %3C num%5Bmid%5D
 %0A       
@@ -1377,18 +1377,16 @@
         
-//
 if (num%5B
@@ -1404,24 +1404,108 @@
 d%5D) l = mid;
+ // revert to the original solution. when mid == l, should avoid l = mid; dead loop.
 %0A           
@@ -1501,26 +1501,24 @@
             
-//
 else r = mid
@@ -1562,16 +1562,26 @@
 ; //
-l:max, r
+num%5Bl%5D:max, num%5Br%5D
 :min

Revert to the original solution.