Question: 

题目：

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.

 

Attention：

Rotated Sorted Array 有一点特性， nums[start] > nums[end]，否则就是 UnRotated Sorted Array 了。思路如下：

• If nums[start] < nums[end], ==> UnRotated ==> return nums[start]
• Else 取 disorder 的一半，踢掉大值，进行下一次找寻。　

这里的 start, mid, end 加减一进行下一步 method call，踢掉大值，也可以防止死循环。

下面的代码，使用了 while(start < end) {} 代替 原 Recursion 实现。其时间复杂度都是 O(logn).

 

1 public int findMin(int[] nums) { 2     if(nums == null || nums.length == 0) { 3         return 0; 4     } 5      6     int start = 0; 7     int end = nums.length - 1; 8     int res = nums[start]; 9     10     while(start < end) {11         int mid = (start + end)/2;12         if(nums[start] < nums[end]) {13             return nums[start];14         } else if(nums[start] > nums[mid]) {15             start++;16             end = mid;17             res = Math.min(res, nums[mid]);18         } else if(nums[end] < nums[mid]) {19             start = mid + 1;20             res = Math.min(res, nums[end]);21         }22     }23     24     return res;25 }