Friday, March 20, 2015

Find Minimum in Rotated Sorted Array -- Leetcode

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.

Answer:

public class Solution {
    public int findMin(int[] num) {
       
        int start=0, end=num.length-1;
       
        while(start+1 < end){      //ensure: start != mid != end  
             int mid = start + (end-start)/2;
           
             if(num[mid] < num[end]){
                 end = mid;
             }
             else{
                 start = mid;
             }
        }
       
        if(num[start]<num[end]){
            return num[start];
        }
        return num[end];
    }
}

No comments:

Post a Comment