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.


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.


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