# 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
a[]={4,5,6,7,1,2,3}.

For the purpose of understanding how to rotate an array referhttps://prepinsta.com/array-rotation/

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*/
{
if(high<low)
return -1;
if(high==low)
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;

if(arr[mid]<arr[high])
findpivot(arr,0,mid-1);
else if( arr[mid]>arr[high])
findpivot(arr,mid,high);
}
int main() {
int n,i,key,k;
cin>>n;
int arr[n];
for(i=0;i<n;i++)
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.
if(k==-1)
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;
}
[/code]

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

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

• Peeyush

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;

cout<>search_element;

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

if(location != -1)
{
cout<<"Search element found at"<<location<<" location"; //Printing the result.
}
else
{
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;
}