Program to Search an Element in a Sorted and Rotated Array

  • Write a program in C to search an element in a sorted array which is also rotated by an unknown position.

Given an sorted integer array of size N which is also rotated by an unknown position. We have to search an element in input array. Input Array is not monotonically increasing as it is rotated at some unknown pivot element.
For Example :

Sorted Array : 1 2 3 4 5 6 7 8
Rotated Array : 4 5 6 7 8 1 2 3
Element to Search : 6
1 is the Pivot Element
6 found at index 2

Let inputArray be a sorted and rotated integer array of size N and we want to search K.

Algorithm to search an element in sorted and rotated array.
This is a two step algorithm:
  1. First find the pivot element in input 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.
  2. If K is >= inputArray[0], then binary search on left sub array otherwise binary search on right sub array.
Time Complexity : O(Logn) 
#include <stdio.h>

int binarySearch(int array[], int left, int right, int key) {
   /* Recursion termination condition */
   if (right < left) /* Element not found */
       return -1;
    
   /* calculate middle index */
   int middle = (left + right)/2;
   
   if (key == array[middle])/* Key found */
       return middle;
       
   if (key > array[middle]){
      /* Search Key in right half of  array */
       return binarySearch(array, (middle + 1), right, key);
   } else {
       /* Search key in left half of array */
       return binarySearch(array, left, (middle -1), key);
   }
}

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 searchElement(int *array, int size, int key) {
   /* Find the pointe of rotation */
   int pivot = getPivotElement(array, 0, size-1) + 1;
 
   /* IF pivt index is -1, means our search vanished */
   if (pivot == -1)
       return binarySearch(array, 0, size-1, key);
 
   if (array[pivot] == key)
       return pivot;
   /* Using binary search, search key in both sub array */
   if (array[0] <= key) {
       /* Search in left side of pivot */
       return binarySearch(array, 0, pivot-1, key);
   } else {
       /* Search in right side of pivot */
       return binarySearch(array, pivot+1, size-1, key);
   }
}

int main(){
    int array[11] = {16, 18, 22, 25, 1, 3, 5, 6, 7, 10, 14};
 
    printf("%d found at index : %d \n", 22, searchElement(array, 11, 22));

    return 0;
}
Output
22 found at index : 2
Posted by
Labels: ,