Table of Contents
Introduction
Let’s imagine a scenario in which we have a rotated sorted array of distinct elements, i.e., sorted in ascending order then rotated around some pivot. Now, we have to search a given element in this rotated sorted array. Let’s take an example-
In the above example, the initial array is sorted in ascending order from 7 to 13. Suppose we rotate it by three positions towards the left. We get a new array sorted from 10 to 13 and 7 to 9. If we had to search any element in the initial array, it is an easy task as we can use binary search, which will take O(logN) time for searching. But that’s not the case with the rotated sorted array.
So let’s find out how we can search any element in the rotated sorted array of distinct elements –
Though there could be many approaches to solve this problem, we will be focusing on the two main methods.
- The naive method starts with finding the pivot in the array and dividing it into subarray around this pivot, and performing a binary search on the sub-array containing the key.
- The second version is an optimized version of this approach which uses a modified binary search.
Let’s learn both these methods in detail one after another-
The Naive Approach
The naive approach to solving this problem starts with finding the pivot element by traversing the array to find an element lesser than its previous element. Then we divide the array into two subarrays around the pivot element. Then we apply binary search in one of the sub-array to find the given element.
Algorithm
- Take the array and key from user input.
- Traverse the array to find the pivot element.
- Divide the array into two subarrays around the pivot.
- Use binary search on one of the arrays by the following condition-
- Use the binary search in the left subarray. If the element searched is greater than the element at the 0th index,
- Use the binary search in the right subarray otherwise.
- If we find the element, return it. if an element is not found, return -1.
Implementation of the Naive Approach
#include <bits/stdc++.h>
using namespace std;
// Binary search function.
int binarysearch(int ar[], int left, int right, int k)
{
if(right<left)
{
return -1;
}
//Finding the middle element.
int mid = (left + right)/2;
//When the middle element is equal to the key.
if(k==ar[mid])
{
return mid;
}
//When the middle element is smaller than the key.
if(k>ar[mid])
{
return binarysearch(ar, mid+1, right, k);
}
//When a middle element is greater than the key.
return binarysearch(ar, left, mid-1, k);
}
//Function to find the pivot.
int getpivot(int ar[], int left, int right)
{
//Base cases.
if(right<left)
{
return -1;
}
if(right==left)
{
return left;
}
//Finding the middle element.
int mid=(left+right)/2;
//When the middle element is the pivot.
if(mid<right && ar[mid]>ar[mid+1])
{
return mid;
}
//When the element before the middle is the pivot.
if(mid>left&&ar[mid]<ar[mid-1])
{
return mid-1;
}
//For pivot lying between left and middle element.
if(ar[left]>=ar[mid])
{
return getpivot(ar, left, mid-1);
}
//For pivot lying between middle element and right.
return getpivot(ar, mid+1, right);
}
//Driver function.
int main()
{
//Taking array size and key as input.
int n, k;
cout<<"Enter the number of elements in the array, and the value to be searched."<<endl;
cin>>n>>k;
//Declaring the array.
int ar[n];
cout<<"Enter array elements-"<<endl;
//Taking input in the array.
for(int i=0;i<n;i++)
{
cin>>ar[i];
}
//Function call to get pivot.
int pivot = getpivot(ar, 0, n - 1);
// Index will be the index of the key in the array. If the
//key is not present it will be equal to -1.
int index;
//Function call to perform binary search.
//If pivot == -1 then the array is not rotated, and we can simply do a binary search over the entire array.
if(pivot==-1)
{
index = binarysearch(ar, 0, n-1, k);
}
else if(ar[pivot] == k)
{
index = pivot;
}
else if(ar[0] <= k)
{
index = binarysearch(ar, 0, pivot-1, k);
}
else
{
index = binarysearch(ar, pivot+1, n-1, k);
}
//Printing the result.
cout<<index<<endl;
return 0;
}
Input-
Enter the number of elements in the array and the value to be searched. 7 8 Enter array elements- 10 11 12 13 7 8 9
Output-
5
The time complexity of this algorithm is O(logN), as we are using binary search.
The space complexity of this algorithm is O(1), as no extra space is required.
The Optimized Approach
Another way to solve this problem is a modified version of the basic approach so that rather than doing multiple traversals of the array, we can search the given element in one traversal. in this approach, and we start with picking the middle element then choosing the sorted array among the left and right subarray. Then we compare the key with the extreme values of these subarrays to choose one for making the recursive calls for the above steps, and we keep doing that until either we find the key or return -1.
Algorithm
- Take the array and key from user input.
- Find the middle element of the array as mid= (left+right)/2.
- If the middle element is equal to the key, return mid.
- Check if the left subarray is sorted( one of both sub-arrays is always sorted)-
- Check the extreme values of the left subarray. If the key lies between it, recursively call step 2 for it.
- Otherwise, recursively call step 2 for the right subarray.
- Otherwise, the right subarray is sorted-
- Check the extreme values of the right subarray. If the key lies between it, recursively call step 2 for it.
- Otherwise, recursively call step 2 for the left subarray.
- Keep making recursive calls until we either find the key or reach the base case.
Implementation of the Optimized Approach
#include <bits/stdc++.h>
using namespace std;
//Function to return the position of the key.
int findpos(int ar[], int left, int right, int k)
{
//Base case.
if(right<left)
{
return -1;
}
//Finding the middle element.
int mid = (left + right)/2;
//When the middle element is equal to the key.
if(k==ar[mid])
{
return mid;
}
//To check if the left array is sorted.
if(ar[left]<=ar[mid])
{
//To check if key belongs to left subarray.
if(k>=ar[left]&&k<=ar[mid])
{
return findpos(ar, left, mid-1, k);
}
return findpos(ar, mid+1, right, k);
}
//If the above condition fails then the right array is sorted.
//Now, check if key belongs to right subarray.
if(k>=ar[mid]&&k<=ar[right])
{
return findpos(ar, mid+1, right, k);
}
return findpos(ar, left, mid-1, k);
}
//Driver function.
int main()
{
//Taking array size and key as input.
int n, k;
cout<<"Enter the number of elements in the array, and the value to be searched."<<endl;
cin>>n>>k;
//Declaring the array.
int ar[n];
cout<<"Enter array elements-"<<endl;
//Taking input in the array.
for(int i=0;i<n;i++)
{
cin>>ar[i];
}
//Function call.
int index = findpos(ar, 0, n - 1, k);
//Printing the result.
cout<<index<<endl;
return 0;
}
Input-
Enter the number of elements in the array and the value to be searched. 7 9 Enter array elements- 10 11 12 13 7 8 9
Output-
6
The time complexity of this algorithm is O(logN), as we are using binary search.
The space complexity of this algorithm is O(1), as no extra space is required.
Frequently Asked Questions
We can rotate a sorted array by shifting all the elements in the cyclic order, i.e., the first element is moved to the rightmost position while shifting towards the left.
To search a target value in a rotated sorted array, we start with finding the pivot element of the array, i.e., the smallest element. Then we run a binary search on the subarray, which could have the target value. This approach can also be modified with the help of recursion. In the modified approach, we will pick the middle element directly and then recursively call the division for the subarray. (sapns2.com) Here the subarray for the next step is chosen by checking if they are sorted as only one subarray can be sorted if the pivot is not in the middle.
We can check if an array is sorted or not by traversing through it, and if we don’t encounter a number that is smaller than its previous number, it is sorted.
Quicksort is generally considered the fastest algorithm, with time complexity of O(N*logN).
The binary search algorithm is best for sorted arrays.
Key Takeaways
in this blog, we learned about searching an element in a rotated sorted array of distinct elements-
- We started with the brute force approach, which first finds the pivot element in the array by checking each element if it is smaller than its previous element. Then, we divide the array into two subarrays, check which can contain the asked element, and call binary search for that subarray until we either reach the base case or get the element.
- The second approach is an optimized version of the brute force approach. In this method, we find the middle element of the array, divide it into two subarrays, pick the one subarray, check if it is sorted, then check if it contains the asked element. If yes, make the recursive call with it, or use the other subarray for the recursion.
Visit here to learn more about arrays. And practice similar problems on CodeStudio. If you liked this blog, share it with your friends.
By: Gorakhnath Yadav
