Program to search the element in Sorted Rotated Pivoted array

Sorted Rotated Pivoted array means the sorted array is rotated through the pivot element.The element in a sorted array can be find using binary search in O(logn) time.But if the sorted array is rotated through some pivot element then how to search for an element in that array.Suppose take sorted array 1 2 3 4 5 it might become 3 4 5 1 2 after rotating at Pivot element 5.Pivot element can be found by the idea that the only element whose next element is smaller then pivot element in an array.So here is the program to find the element in a sorted rotated pivoted array.

Our first task is to find a pivot element in an array.The above idea of  pivot element is used to find the pivot element in an array.

int findpivot(int a[],int low,int high)
{
int mid=(low+high)/2;

if(a[mid]>a[mid+1])        // if middle element is greater then its next element then it is pivot element as it is the          
                                         only element whose next element is smaller then itself.
return mid;

if(a[low]>a[mid])            // if the low element is greater then middle element then search for pivot from low to
                                         mid-1 by calling the same function recursively .

return findpivot(a,low,mid-1);

else                                 //if not then it is in right part call recursively from mid+1 to high

return findpivot(a,mid+1,high);
}

Now we can find the element in sorted rotated pivoted array using the pivot element and doing Binary search.

int pivotedBinarySearch(int a[],int size,int no)
{
int pivot=findpivot(a,0,size-1);

if(a[pivot]==no)              //If number is at pivot element index then return the index pivot

return pivot;

if(a[0]<=no)                   // Now search in subarrays the element to be find using binary search

return Binarysearch(a,0,pivot-1,no);

else'

return Binarysearch(a,pivot+1,size-1,no);
}

Program :


int pivotedBinarySearch(int a[],int size,int no)
{
int pivot=findpivot(a,0,size-1);
if(a[pivot]==no)            
return pivot;
if(a[0]<=no)                  
return Binarysearch(a,0,pivot-1,no);
else
return Binarysearch(a,pivot+1,size-1,no);
}

int findpivot(int a[],int low,int high)
{
int mid=(low+high)/2;
if(a[mid]>a[mid+1])      
return mid;
if(a[low]>a[mid])          
return findpivot(a,low,mid-1);
else                                 /
return findpivot(a,mid+1,high);
}
int Binarysearch(int a[],int low,int high,int no)
{
if(high>=low)
int mid=(low+high)/2;
if(no==a[mid])
return mid;
if(no>a[mid])
return Binarysearch(a,mid+1,high,no);
else
return Binarysearch(a,low,mid-1,no);
}

//This program may not work with Duplicate elements.

Time Complexity - O(logn)