Program to find Pivot Element of a Sorted and Rotated Array

  • Write a program in C to find pivot element of a sorted and rotated array using binary search.

Given an sorted integer array of size N which is also rotated by an unknown position. Input Array is not monotonically increasing as it is rotated at some unknown pivot element. We have to find the pivot element of array.
Pivot element is the only element in input array which is smaller than it's previous element. A pivot element divided a sorted rotated array into two monotonically increasing array.
For Example :

Sorted Rotated Array : 4 5 6 7 8 1 2 3
1 is the Pivot Element

Let inputArray be a sorted and rotated integer array of size N and we want to find the pivot element(minimum element).
By linearly searching input Array
  • In sorted and rotated array, pivot element(minimum element) is the only element which is smaller than it's previous element.
  • Traverse inputArray from index 0 to N-1 and search for an element inputArray[i] which is smaller than previous element inputArray[i-1].
By using modified binary search
Algorithm to find pivot element of a rotated array.
  • Initialize leftIndex and rightIndex to 0 and N-1 respectively.
  • If leftIndex == rightIndex(size of the array is 1), return leftIndex.
  • Find the middle index as (leftIndex + rightIndex)/2. Let middle index be mid.
  • Check if inputArray[mid] is a pivot element. If (inputArray[mid-1] > inputArray[mid] < inputArray[mid+1]) is true then inputArray[mid] is pivot element.
  • If inputArray[leftINdex] >= inputArray[mid] then recursively search on sub left sub array from index leftIndex to mid-1.
  • Else recursively search on sub array from index mid+1 to rightIndex.
Time Complexity : O(Logn)

C program to find pivot element of rotated array

#include <stdio.h>

int getPivotElement(int *array, int left, int right){
   if (right < left) /* Array not rotated */   
       return -1;
   
   /* Only element in sub array */
   if (right == left) 
       return left;
 
   /* Find the mid element */
   int middle = (left + right)/2;
   
   /* Only the pivot element will be 
      more than it's next element */
   if (middle < right && array[middle] > array[middle + 1])
       return middle;

   if (middle > left && array[middle] < array[middle - 1])
       return middle-1;
    
   if (array[left] >= array[middle]){
      /* Pivot element is between left and mid index */
       return getPivotElement(array, left, middle-1);
   } else {
       /* Pivot element is between mid and right index */
       return getPivotElement(array, middle + 1, right);
   }
}

int main(){
    int array[11] = {16, 18, 22, 25, 1, 3, 5, 6, 7, 10, 14};
 
    printf("Pivot Element : %d \n", array[getPivotElement(array, 0, 10) + 1]);

    return 0;
}
Output
Pivot Element : 1
Posted by
Labels: ,