Labels

Friday, February 27, 2015

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.

Naive Way: I think a sorted array is highly related to a binary search approach, especially finding an element. Use the picture I draw in search-in-rotated-sorted-array-ii . There are two situations when doing a binary search approach. It the first scene, when b2 > b1 and e1 > e2, the minimum lies in the second half. It the second scene, whose condition is the opposite, minimum lies in the first half. And what we are looking for is the position where num[i-1] > num[i]. If such position doesn't found, we can return the first element.



 public class Solution {  
   public int findMin(int[] num) {  
     return binarySearch(num, 0, num.length-1);  
   }  
   private int binarySearch(int[] num, int begin, int end){  
     while(begin < end){  
       int middle = (begin+end)/2;  
       if(num[middle] > num[middle+1]) return num[middle+1];  
       if(num[middle] > num[end]) begin = middle+1;  
       else end = middle;  
     }  
     return num[begin];  
   }  
 }  

No comments:

Post a Comment