Searching an element in sorted-rotated array

Searching in Rotated- Sorted Array.

A rotated sorted is the array which has undergone rotation operation after its sorted.
For eg if a[]={1,2 ,3 ,4 ,5 ,6,7} , which is an example of sorted array .
Once it undergoes rotation operation the array becomes

For the purpose of understanding how to rotate an array refer

If the value to be searched in the above array is 5 then the code must return the index at which 5 is present and if the desired element not found then return -1.
This can be implemented using Linear search but it takes O(n) time and thus to reduce the time complexity we implement the binary search.Which takes O(log n) time.

Code:- It is strictly advisable to try yourself once before viewing the solution. You can submit your codes in the comment section below. They will get published on the website after reviewing.

[code language=”cpp”]
#include <iostream>
using namespace std;
int binarySearch(int arr[], int low, int high, int key)
if (high >= low)
int mid = low + (high – low)/2;

// If the element is present at the middle
// itself
if (arr[mid] == key)
return mid;

// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > key)
return binarySearch(arr, low, mid-1, key);

// Else the element can only be present
// in right subarray
return binarySearch(arr, mid+1, high, key);
int findpivot(int arr[], int low, int high)
/* function which finds the pivot element*/
return -1;
return low;
int mid=(low+high)/2;
if(arr[mid]>arr[mid+1])// && mid<high)
return mid-1;
else if(arr[mid]<arr[mid-1] )//&& mid>low)
return mid-1;

else if( arr[mid]>arr[high])
int main() {
// your code goes here
int n,i,key,k;
int arr[n];
cin>>arr[i];// elements of array which are in rotated-sorted manner.
cin>>key;// key holds the element to be found out

k= findpivot(arr,0,n-1); // finding the pivot in array at which roattion has been carried out.
return binarySearch(arr,0,n-1,key);
else if(key==arr[k])
return k;
else if(k>=arr[0] )
return binarySearch(arr,0,k-1,key);

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

return 0;



Thus the element is found in the rotated-sorted array.

2 comments on “Searching an element in sorted-rotated array”

  • Peeyush

    #include //Header file.
    using namespace std;

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

    int main() //Main function.
    int arr[10] = {19, 26, 37, 53, 56, 61, 77, 82, 87, 91};
    int search_element, location=-1;


    location = binarySearch(arr, 0, 9, search_element);

    if(location != -1)
    cout<<"Search element found at"<<location<<" location"; //Printing the result.
    cout<= left)
    middle = (left + right)/2;
    if(a[middle] == search_element) //Checking if elemnet is present at middle.
    return middle+1;
    else if(a[middle] < search_element) //Checking if elemnet is present in greater half.
    return binarySearch(a,middle+1,right,search_element);
    else //Checking if elemnet is present in samller half.
    return binarySearch(a,left,middle-1,search_element);

    return -1;