Searching and Sorting in Rotated Sorted Array  | Part-2

Gorakhnath yadav
Last Updated: May 13, 2022

Introduction-

In the previous blog on the rotated sorted array, we learned about searching in the rotated sorted array with no duplicate elements. In this blog, we will learn about searching an element in a rotated sorted array with duplicate elements. But before diving into the solution, let's see an example and understand the problem thoroughly-

The array given above is sorted from the 8 at the 0th index to 12 and 7 to 8 at the last index. Or we can say that it was a sorted array from 7 to 12, then rotated by three positions in the clockwise direction. Now we have the task of searching the given number in this array. Let's see how we can do that-

Solution using modified binary search-

The idea to solve this problem is very similar to what we used for searching an element in a rotated sorted array with no duplicate elements. We used a modified binary search for this.

 

We start with finding the mid element of the array, divide the array into two subarrays around that middle element, and then pick one subarray to follow the above process recursively. Now we know that for a rotated sorted array, one of the subarrays is sorted. So, we compare the left, right, and mid-value to check which sub-array is sorted.

 

At this step in the rotated sorted array with duplicate elements, all three values left, middle, and right elements could be the same. Then, we won't be able to decide which subarray is sorted. For Example:Let nums = [4 5 6 4 4 4 4] ,mid = 3 and lo = 0, since nums[3] >= nums[0] but the array from 0 to 3 is out of order and not sorted, so we need to modify the previous solution to handle this case.

 

To accommodate the case of left, right, middle elements being equal, we can put a check for this before checking which subarray is sorted. And if all these elements are equal, we will move the left and right counters inwards by one position at a time to find a subarray with different values at the left and right index. let's see an example to develop a better understanding-

In the above example, the left, middle and right elements are equal, so we can't decide which subarray is sorted. But, if we move both the left and right counters one position inwards(i.e left = left +1 and right  = right  - 1), the value of right changes to 7, and we can find that the left subarray is sorted.

Algorithm-

  1. Take the array and key from user input.
  2. Find the middle element of the array as mid= (left+right)/2.
  3. If the middle element is equal to the key, return mid.
  4. If left, right, and middle elements are equal- increase the left counter by 1 and decrease the right counter by 1, and recursively call step 2, with new left and right values.
  5. Check if the left subarray is sorted( one of both sub-arrays is 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.
  1. 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.
  1. Keep making recursive calls until we either find the key or reach the base case.

Implementation of the solution-

#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 handle the  case of duplicate elements.
    if ((ar[left]==ar[mid])&&(ar[right]==ar[mid]))
    {
        ++left;
        --right;
        return findpos(ar, left, right, k);
    }
    //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 key.

7 12

Enter array elements-

8 8 8 8 12 7 8

Output-

4

 

Time Complexity: 

The time complexity of this algorithm is O(logN) in average caseas we are using binary search, however in the worst case the time complexity becomes O(N) when all the elements in the array are the same.

Space Complexity: 

The space complexity of this algorithm is O(1), as no extra space is required.

Frequently asked questions-

  1. How do you rotate a sorted array?
    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.
     
  2. How do you search for a target value in a rotated sorted array with duplicate elements?
    We use a modified version of binary search to search a target value in a rotated sorted array with duplicate elements. It starts with finding the middle element of the array and the array into two subarrays around the middle element. After that, we need to pick one subarray to repeat the process recursively, but before doing that, we check if the left, right, and middle elements are equal. If yes, we increase the left value by one and decrease the right value by one. Then we recursively call the modified binary search with updated values of left and right.
     
  3. How to check if an array is sorted?
    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.
     
  4. Which is the fastest algorithm for searching?
    Binary search is generally considered the fastest searching algorithm, with time complexity of O(logN) considering the behaviour of the problem to be solved is monotonically increasing or decreasing in nature.
     
  5. Which searching algorithm is best for sorted arrays? 
    The binary search algorithm is best for sorted arrays.

Key takeaways-

In this blog, we discussed how we could search an element in a rotated sorted array with duplicate elements-

For this task, we use a modified binary search. It also takes the array, left-right indices, and the key as parameters similar to binary search. Then we find the middle element and divide the array into two subarrays. Now instead of simply checking the subarrays, if they can contain the key. We first check if the left, right, and middle elements are equal. If yes, we increase the left index by 1 and decrease the right index by one. Then make a recursive call for this modified binary search function with these updated parameters. Otherwise, we first check which subarray is sorted and then check which subarray can contain the key. We continue this process with recursion till either we reach the base case or find the key.

Visit here to learn more about arrays. And practice similar problems on CodeStudio. If you liked this blog, share it with your friends.

Was this article helpful ?
7 upvotes

Comments

No comments yet

Be the first to share what you think