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.
Please try solving this problem before jumping on the solution
Click to learn
Subscribe for more updates
Algorithm/Insights
Use modified binary search to find pivot element: 1. If array[0] <= 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.
Like IDeserve?
Support us by whitelisting IDeserve in your ad-blocker.
Thanks, -Team IDeserve
Algorithm Visualization
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[0] < 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)
Contribution
Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.
Saurabh Kumar
Like IDeserve?
Support us by whitelisting IDeserve in your ad-blocker.