[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 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。

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