[LeetCode] Find Minimum in Rotated Sorted Array

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.

     这道题主要是因为是rotated的所以会很麻烦。为了简化，可以每次都将剩下的array cut half every time。

     拿第一个和最中间的那个进行比较。如果依旧是第一个比较小，那么我们就可以只看后半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;  }}

原标题：[LeetCode] Find Minimum in Rotated Sorted Array

关键词：array