Suppose a sorted array is rotated at some pivot unknown to you beforehand.

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

Find the minimum element.

You may assume no duplicate exists in the array.

這道題主要是因為是rotated的所以會很麻煩。為了簡化，可以每次都將剩下的array cut half every time。

拿第一個和最中間的那個進(jìn)行比較。如果依舊是第一個比較小，那么我們就可以只看后半half。（rotated的話，第一個肯定比最后一個大）

反之則我們肯定要看前半部分了。（比中間那個小的肯定是它前面的一個，sorted的嘛。）

然后while的條件是start<end-1，因為start肯定！=end。

不過最后還是要比較一下目前的Min,nums[start],nums[end]，specail case如果middle one or first one就是smallest呢。

代碼如下。~

public class Solution {    public int findMin(int[] nums) {      //special case      if(nums.length==0){          return nums[0];      }      int start=0;      int end=nums.length-1;      int min=nums[0];           while(start<end-1){ //start and end couldn't be equal           int a=(start+end)/2;          if(nums[start]<nums[a]){              min=Math.min(min,nums[start]);              start=a+1;          }else{              min=Math.min(min,nums[a]);              end=a-1;          }      }      min=Math.min(min,Math.min(nums[start],nums[end]));      return min;    }}