Sunday, March 2, 2014

Find the pivot element in the rotated sorted array

A sorted array is rotated around a pivot element. Find the pivot element in the rotated sorted array.
 
Analysis

Lets start with an example
Original array:           2, 4, 6, 8, 9, 10, 12, 15
Rotated array:           10, 12, 15, 2, 4, 6, 8, 9
Output:                      3




One important observation is that the pivot element lies between two elements i, j iff i > j and a[i]  < a[j] 
The ith element is the pivot element iff a[i-1] > a[i] < a[i+1]

With the above two observations we can modify the basic binary search technique to find the pivot element

Below piece of code returns the pivot element

int pivot(int * a, int len) {
    int l = 0, r = len - 1;
    if(a[l] < a[r])
        return 0;
    while (true) {
        if(l == r) return l;
        int m = (l + r)/2;
        if(a[m] < a[m-1] && a[m] < a[m+1])
            return m;
        if (a[m] > a[r])
            l = m + 1;
        else r = m;
    }
}

 

No comments :

Post a Comment