Monday, March 2, 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.
Note: binary search
Run time complexity is O(logn), space complexity is constant space
public class Solution {
    public int findMin(int[] num) {
        if(num == null || num.length == 0)
            return 0;
        
        int l = 0, r = num.length - 1;
        while(l < r) {
            int mid = (l + r) / 2;
            if(num[mid] > num[r]) {
                l = mid + 1;
            }else {
                r = mid;
            }
        }
        return num[l];
    }
}
Or:
public class Solution {
    public int findMin(int[] num) {
        if(num == null || num.length == 0) 
            return 0;

        int start = 0;
        int end = num.length - 1;
        int result = num[0];
        
        while(start < end - 1) {
            int mid = (end + start) / 2;
            
            if(num[mid] > num[start]) {
                result = Math.min(num[start], result);
                start = mid + 1;
            }else if(num[mid] < num[start]) {
                result = Math.min(num[mid], result);
                end = mid - 1;
            }else {
                start++;
            }
                
        }
        result = Math.min(num[start], result);
        result = Math.min(num[end], result);
        return result;
    }
}

No comments:

Post a Comment