Find Minimum element 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.

Discussion :

Case 1 : No duplicate exists in the array


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


Case 2 : Duplicate exists in the array


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

Comments

Popular posts from this blog

Longest Subarray with Sum greater than Equal to K

Search in Rotated Sorted Array

Consistent Hashing