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

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