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

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

**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