Search an element in a sorted and rotated array

Search an element in a sorted and rotated array

/* Program to search an element in a sorted and pivoted array*/

#include <stdio.h>

int findPivot(int[], int, int);

int binarySearch(int[], int, int, int);

/* Searches an element key in a pivoted sorted array arrp[]

   of size n */

int pivotedBinarySearch(int arr[], int n, int key)

{

   int pivot = findPivot(arr, 0, n-1);

   // If we didn't find a pivot, then array is not rotated at all

   if (pivot == -1)

       return binarySearch(arr, 0, n-1, key);

   // If we found a pivot, then first compare with pivot and then

   // search in two subarrays around pivot

   if (arr[pivot] == key)

       return pivot;

   if (arr[0] <= key)

       return binarySearch(arr, 0, pivot-1, key);

   return binarySearch(arr, pivot+1, n-1, key);

}

/* Function to get pivot. For array 3, 4, 5, 6, 1, 2 it returns

   3 (index of 6) */

int findPivot(int arr[], int low, int high)

{

   // base cases

   if (high < low)  return -1;

   if (high == low) return low;

 int mid = (low + high)/2;   /*low + (high - low)/2;*/

   if (mid < high && arr[mid] > arr[mid + 1])

       return mid;

   if (mid > low && arr[mid] < arr[mid - 1])

       return (mid-1);

   if (arr[low] >= arr[mid])

       return findPivot(arr, low, mid-1);

   return findPivot(arr, mid + 1, high);

}

/* Standard Binary Search function*/

int binarySearch(int arr[], int low, int high, int key)

{

   if (high < low)

       return -1;

   int mid = (low + high)/2;  /*low + (high - low)/2;*/

   if (key == arr[mid])

       return mid;

   if (key > arr[mid])

       return binarySearch(arr, (mid + 1), high, key);

   return binarySearch(arr, low, (mid -1), key);

}

/* Driver program to check above functions */

int main()

{

   // Let us search 3 in below array

   int arr1[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};

   int n = sizeof(arr1)/sizeof(arr1[0]);

   int key = 3;

   printf("Index of the element is : %d",pivotedBinarySearch(arr1, n, key));

   return 0;

}

Output:

Index of the element is : 8

Example:

Input: arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};

        key = 3

Output: Found at index 8

Input  : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};

         key = 30

Output : Not found

Input : arr[] = {30, 40, 50, 10, 20}

        key = 10  

Output : Found at index 3