# Find pivot in a sorted rotated array

Given a sorted integer array which is rotated any number of times, find the pivot index i.e. index of the minimum element of the array.

## Algorithm/Insights

Use modified binary search to find pivot element:
1. If array <= array[length of array - 1], it means the array is not rotated, so return 0.
2. Initialize start = 0, end = length of array - 1.
3. Repeat following steps till start <= end
a). Set mid = (start+end)/2.
b). If mid+1 is pivot, then break.
c). If array[start] <= array[mid], it means from start to mid, all elements are in sorted order.
Set start = mid+1, so that we look for pivot in second half of the array.
d). Else set end = mid-1, to look for pivot in first half.

## Code Snippet

```
package com.ideserve.saurabh.questions;

public class FindPivotInSortedRotatedArray {

// O(n) solution - Linear Search
public static int findPivotLinear(int[] array) {
int pivot = -1;

if (array != null && array.length > 0) {

pivot = 0;
for (int i = 0; i < array.length - 1; i++) {
if (array[i] > array[i + 1]) {
pivot = i + 1;
break;
}
}
}
return pivot;
}

// O(log n) solution - Binary Search
public static int findPivotBinarySearch(int[] array) {

if (array == null || array.length == 0) {
return -1;
}

// Case when array is not rotated. Then first index is the pivot
if (array.length == 1 || array < array[array.length - 1]) {
return 0;
}

int start = 0, end = array.length - 1;

while (start <= end) {

int mid = (start + end) / 2;
// check if mid+1 is pivot
if (mid < array.length-1 && array[mid] > array[mid+1]) {
return (mid + 1);
} else if (array[start] <= array[mid]) {
// If array[start] <= array[mid],
// it means from start to mid, all elements are in sorted order,
// so pivot will be in second half
start = mid + 1;
} else {
// else pivot lies in first half, so we find the pivot in first half
end = mid - 1;
}
}

return 0;
}

public static void main(String[] args) {

int array[] = { 5, 4 };
findPivotBinarySearchTest(array);
}

public static void findPivotLinearTest(int array[]) {
int index = findPivotLinear(array);
System.out.println("Pivot "
+ (index >= 0 ? (" found at index " + index) : " not found!"));
}

public static void findPivotBinarySearchTest(int array[]) {
int index = findPivotBinarySearch(array);
System.out.println("Pivot "
+ (index >= 0 ? (" found at index " + index) : " not found!"));
}
}
```

## Order of the Algorithm

Time Complexity is O(log n)
Space Complexity is O(1)