Searching an element in sorted-rotated array

June 23, 2019

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() {
// your code goes here
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

    #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;

    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;
    }