Search an Element in a Rotated Sorted Array

Given a sorted rotated array arr[] having N number of elements and a target element K. We are supposed to find the 0 (zero) based index (indexing starts from 0 rather than 1) of the target element if it exists and return -1 if it doesn’t.

Let us assume for now that duplicates don’t exist, we will handle the case of duplicates in the latter part of the article.

Let us say the original array was as follows:

This array is sorted in the ascending order. The rotated array is nothing but say M rotations performed in a clockwise direction on the same array. In this case, let the value of M be 3 in the clockwise direction. The array is transformed as below:

• After first rotation, $M = 1$ 26 28 40 54 64 75 99 11
• After second rotation, $M = 2$ 28 40 54 64 75 99 11 26
• After third rotation, $M = 3$ 40 54 64 75 99 11 26 28

Let the target element Kbe 26 and we are supposed to find the answer in $log(n)$ Time complexity.

Approach 1

We are supposed to search in a rotated sorted array in $O(log(N))$ time complexity, we can use Binary Search. The idea is very simple, We will find the pivot index i.e. the index from where condition $arr[i] > arr[i+1]$ satisfies.

This is the index where the rotation has happened. We will simply perform a binary search on the two arrays formed from 0th to ith index and (i+1)th to (N-1)th, where N is the number of elements in the array.

Now, the challenge is to find the pivot index with $O(log(N))$ time complexity. We can again use Binary Search to find the pivot index. The main idea for finding the pivot index is as follows:

• The pivot index i satisfies the condition $arr[i] > arr[i+1]$ i.e. the only index for which the current element is greater than the next element.
• Now we can have the search space starting from 0th index to (N-1)th index which will contribute to calculating mid.
• Now, if the element at mid index is greater than the next element(mid+1), mid is our pivot and we can return mid. Similarly, if the element at mid is smaller than the previous element (mid-1) then mid-1 is our pivot index.
• If none of the above conditions is satisfied, we can shorten the search space. One of the two halves will be sorted as only one rotation is performed on the array. Pivot exists in the subarray where rotation is performed.
• If the rotation has happened in the left half, then the element at the low index will be greater than mid.
• Otherwise, the left half is sorted, and in the right half element at high is less than mid i.e. rotation happened in the right half.
• We can recursively call the function to find the pivot index based on the condition.
• Once the pivot index is found, we can run a binary search on both the sub-arrays as individual sub-arrays are sorted.

Steps to Take

Follow the steps to perform above mentioned idea to search in the sorted rotated array:

Finding Pivot:

• Let the function be called pivotBinarySearch() that takes an array, low and high starting from the 0th index till the last one and calculates the mid value using the formula $mid = l + (h-l)/2$.
• If the value at index mid is greater than the one at index mid+1 return mid. If the value at index mid-1 is greater than the one at mid then return mid-1.
• Else, if the value at the low position is greater than at the mid position call the function pitvotBinarySearch on the left half else call it on the right half.

Finding Target Index

• Call the function pivotBinarySearch() to get the index of the pivot element.
• Call BinarySearch on the left half and right half. If both return -1, return -1. Else return the one that returns an actual index.

Illustration

Finding Pivot:

Considering the same example we used above let us see how this works:
The target is 26

low = 0, high = 7

Step 1:

$mid = 0 + (7 – 0) / 2 = 3$

The element at index 3 is 75, which is not greater than the element at index 4 (99).
The element at index 3 is not less than the element at index 2 (64). It implies that we didn’t find the pivot in mid or mid - 1.

Step 2:

$75$(mid)$ > 40$(element at low)

The array is sorted till mid, as the element at mid is greater than the element at low. Thus, the pivot must exist after mid and we move the low pointer as mid+1.

low = 4, high = 7

Step 3:

$mid = 4 + (7 – 4) / 2 = 5$

The element at index 5 is 11, which is less than the element at index 4 (99).

Binary Search on Left Sub-array:

low = 0, high = 4

Step 1:

$mid = (0 + 4) / 2 = 2$

The element at index 2 is 64, which is less than the target value (26).

Step 2:

$26 < 64$, move the high pointer to mid-1

low = 0, high = 1

Step 3:

$mid = (0 + 1) / 2 = 0$

The element at index 0 is 40, which is less than the target value (26).

Step 4:

$26 > 40$, move low pointer to mid + 1

low = 1, high = 1

The search ends without finding the element 26 in the array and thus, it returns -1.

Binary Search on Right Sub-array:

low = 5, high = 7

Step 1:

$mid = (5 + 7) / 2 = 6$

The element at index 6 is 26, which is equal to the target value (26).

Binary search ends:

Target value 26 is found at index 6 after the pivot.

Implementation

#include <bits/stdc++.h>
using namespace std;

// Standard Binary Search function
int binarySearch(int A[], int low, int high, int key)
{
    while(s <= e){

        int mid = s + (e-s)/2;

        if(A[mid] == key) return mid;

        else if(A[mid] < key) s = mid+1;  

        else e = mid - 1;
    }

    return -1;
}

// Function to get pivot. For array | 40 | 54 | 64 | 75 | 99 | 11 | 26 | 28 |
// it returns 4 (index of 99)
int pivotBinarySearch(int A[], int low, int high)
{
    // Base cases
    if (high < low)
        return -1;
    if (high == low)
        return low;

    // Calculate middle index: low + (high - low)/2;
    int mid = (low + high) / 2;
    if (mid < high && A[mid] > A[mid + 1])
        return mid;

    if (mid > low && A[mid] < A[mid - 1])
        return (mid - 1);

    if (A[low] >= A[mid])
        return pivotBinarySearch(A, low, mid - 1);

    return pivotBinarySearch(A, mid + 1, high);
}

// Searches an element key in a pivoted sorted array A[] of size n
int pivotedBinarySearch(int A[], int n, int key)
{
    int pivot = pivotBinarySearch(A, 0, n - 1);

    // If we didn't find a pivot, then the array is not rotated at all
    if (pivot == -1)
        return binarySearch(A, 0, n - 1, key);

    // If we found a pivot, then first compare it with the pivot
    // and then search in two subarrays around the pivot
    if (A[pivot] == key)
        return pivot;

    if (A[0] <= key)
        return binarySearch(A, 0, pivot - 1, key);

    return binarySearch(A, pivot + 1, n - 1, key);
}

// Driver program to check the above functions
int main()
{
    // Array to search: | 40 | 54 | 64 | 75 | 99 | 11 | 26 | 28 |
    int A[] = { 40, 54, 64, 75, 99, 11, 26, 28 };
    int n = sizeof(A) / sizeof(A[0]);
    int key = 26;

    // Function calling
    cout << "Index of the element is: "
         << pivotedBinarySearch(A, n, key);

    return 0;
}

Output

The index of the element is: 6

Complexity Analysis

• Time complexity as specified is $O(log(N))$ only. Only one call is made to the function pivotBinarySearch() which takes $O(log(N))$ and two calls to binary search which again takes $O(log(N))$.
• As we are not using any exptra space, Auxiliary Space Complexity is $O(1)$.

Approach 2: Direct Binary Search Without Finding Pivot

Instead of 2 binary search calls, we can find the target element in one binary search call. The idea is to modify the binary search algorithm such that we can recursively call it to find the target element. We have to remember that at least one of the subarrays will always be sorted.

This can be divided into three cases:

Case 1:

Where mid element is the target element, we return the mid element.

Case 2:

Left sub-array is sorted. Here again there are two possibilities either the target exists in the left subarray or the right subarray. To figure out we can check if the target is greater than or equal to low and is smaller than or equal to mid. If the condition is satisfied we can simply move high to mid - 1 i.e. left subarray. We can find it in the right subarray i.e. move low to mid+1 and search in mid + 1 to high.

Case 3:

The right sub-array is sorted. We again check if the element exists in the right sub-array by checking the target being greater than mid and smaller than high. If it satisfies the condition we move the low to mid+1 i.e. we search in the right subarray. Otherwise, we search in the right subarray i.e. move the high to mid-1.

Here, Binary Search works on rotated as well as sorted arrays. This is helpful in case our search space only has a sorted array.

Steps to Take

Let us now look at the steps we can follow to apply the algorithm to search in sorted rot

• Check if the element at the mid index equals the target. If it does return the mid-index.
• Else We check for case 2. We will compare the target element with the mid to be less than or equal to mid and greater than the element at low. Then this becomes our search space i.e. low to mid-1.
• If the condition doesn’t satisfy, then we look in the right sub-array i.e. mid+1 to high.
• If the left subarray is not sorted then definitely the right subarray is sorted. In this case, we check if the target is less than or equal to the element at high and greater than mid+1. Thus, we reduce our search space from mid+1 to high.
• If this condition also fails then we can simply look in the left subarray i.e. low to mid-1.

Illustration

Let our array be as follows and the target element is 47.

Initial values:

• l (starting index): 0
• h (ending index): 9
• key: 47

First Iteration:

• mid is calculated as $0 + (9 – 0) / 2 = 4$.
• A[mid] is 23, which is less than the key 47.
• Since A[mid] is less than A[l], we enter the “else” block.
• A[mid] is less than the key, but A[h] (82) is greater than the key.
• So, we adjust l to mid + 1, which becomes 5.

Second Iteration:

• mid is calculated as $5 + (9 – 5) / 2 = 7$.
• A[mid] is 63, which is less than the key 47.
• Since A[mid] is not greater than or equal to A[l], we enter the “else” block.
• A[mid] is greater than the key, and A[h] (82) is also greater than the key.
• So, we adjust h to mid - 1, which becomes 6.

Third Iteration:

• mid is calculated as $5 + (6 – 5) / 2 = 5$.
• A[mid] is 47, which is equal to the key we’re searching for.
• We found the key at index 5, so we returned 5 as the result.
• The search is successful, and the key 47 is found at index 5.

Implementation

class Solution{
public:
    int search(int A[], int l, int h, int key){
        // l: The starting index
        // h: The ending index, you have to search the key in this range

        // Perform a binary search on the rotated sorted array
        while(l <= h){
            int mid = l + (h-l)/2; // Calculate the middle index

            if(A[mid] == key) // If the middle element is equal to the key, return its index
                return mid;

            if(A[mid] >= A[l]){ // If the left half is sorted
                if(A[mid] >= key && A[l] <= key) // If the key lies within the sorted left half
                    h = mid - 1; // Adjust the search range to the left of the middle
                else
                    l = mid + 1; // Adjust the search range to the right of the middle
            }else{ // If the right half is sorted
                if(A[mid] <= key && A[h] >= key) // If the key lies within the sorted right half
                    l = mid + 1; // Adjust the search range to the right of the middle
                else
                    h = mid - 1; // Adjust the search range to the left of the middle
            }
        }

        // Key not found in the array
        return -1;
    }
};
// Driver program
int main()
{
    int arr[] = { 91, 105, 112, 10, 23, 47, 58, 63, 76, 82 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 3;
    int i = search(arr, 0, n - 1, key);

    if (i != -1)
        cout << "Index: " << i << endl;
    else
        cout << "Key not found";
}

Output

Index: 5

Complexity Analysis

As we are using binary search,

• Time complexity is $O(log(N))$ and
• Space complexiaty is $O(1)$ as no extra space is required.

Handling Duplicates

Let us say the array is as follows with duplicates:

Input: {5,5,6,6,8,9,1,2,5}

key: 6

Output: 1

The array is sorted and rotated as in the previous case the only change is here we also have duplicates. Our task is to find the index of the key. In case of multiple occurrences of the key, return any one index as output in $O(Log(N))$ time.

The idea for the solution is the same as the previous approach with a slight change. The cases we are supposed to handle were $A[low] == A[mid]$ and $A[mid] == A[high]$.

This can be checked in the beginning itself and if this condition is true, increase the low pointer by 1, decrease the right pointer by 1 and again iterate with new low and high values.

The code for the above approach is as follows:

#include <iostream>
using namespace std;

// Function to return the position of the key.
int findPos(int ar[], int left, int right, int k) {
    while (left <= right) {
        int mid = (left + right) / 2;

        if (ar[mid] == k) {
            return mid; // Key found at index mid.
        }

        if ((ar[left] == ar[mid]) && (ar[right] == ar[mid])) {
            ++left;
            --right;
            // Skip duplicates on both ends.
        }
        else if (ar[left] <= ar[mid]) {
            if (k >= ar[left] && k <= ar[mid]) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
            // Adjust the search range for the left-sorted segment.
        }
        else {
            if (k >= ar[mid] && k <= ar[right]) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
            // Adjust the search range for the right sorted segment.
        }
    }
    return -1; // Key not found in the array.
}

int main() {
    int ar[] = {5, 5, 6, 6, 8, 9, 1, 2, 5};
    int n = sizeof(ar) / sizeof(ar[0]);
    int key = 2;

    int index = findPos(ar, 0, n - 1, key);

    if (index != -1) {
        cout << "Position of " << key << " in the array: " << index << endl;
    }
    else {
        cout << "Key not found in the array." << endl;
    }

    return 0;
}

Output:

Position of 6 in the array: 2

FAQs

Q. What’s the role of the middle element in the Search Algorithm?

A. The middle element helps us reduce the search space to the left half or the right half in Binary Search. It helps us determine the section in which the target element may be present.

Q. Are there any edge cases we should consider in the first approach?

A. Yes the pivot element can be equal to the target element so that must be checked before diving the array. Also, if the result is found in the left half then don’t call the right half.

Q. How does the second approach differ from the first?

A. In the first approach, finding the pivot point is a separate step before binary search. The second approach combines both steps into the binary search process.

Q. As the time and space complexities of both the approaches are the same compare the two approaches.

A. The first approach might be preferred when duplicates are fewer and pivot identification is straightforward. The second approach is a more efficient choice when handling arrays with a significant number of duplicate elements.

Conclusion

• We are given a sorted array, rotated, and a target key. We are supposed to return the index of occurrence of the target in $O(log(N))$ time.
• The first approach to search in a sorted rotated finds the pivot i.e. index where rotation began and divides the array into two parts. A binary search is then performed on both subarrays to get the index of the target value.
• The second approach doesn’t require finding a pivot. Here, the Binary Search Algorithm is only modified to get the result. Instead of finding the pivot point, the algorithm directly compares the middle element to the target element.
• It determines whether the target element lies in a segment that is guaranteed to be sorted. If it does, the algorithm restricts the search to that segment; otherwise, it searches the other segment.