How to Find Element in Rotated Sorted Array?

In this article, we are going to find the element in a rotated sorted array using the programs in different computer languages like Java and C++. We are going to use different approaches to find the element in rotated sorted array. We are also going to find the Time complexity and the Space complexity of the program.

Finding the pivot point, splitting the array into two smaller arrays, and running a binary search are the intended steps.

The key concept for locating a pivot is:

• In an array that has been rotated and sorted (in increasing order), the pivot element is the only one for which the element after it is smaller.
• Pivot can be located via binary search, which is based on the previous concept.
• The element at l will obviously be larger than the element at mid if rotation has occurred in the left half of the search space for indices in the range [l, r] where the middle index is mid.
• The left half will be sorted without it, but the element at mid will be larger than the element at r.
• Subdivide the array into two when the pivot has been located.

Every sub-array has been sorted now so that binary search can be used to find an element.

Implementation of the Program

The following steps are used to implement the program. The goal is to locate the key within an N-dimensional, sorted, and rotated array called arr[].

• Utilize binary search to determine the pivot point. The initial array index will be low, while the last array index will be high.
• We will determine the midpoint based on the high and low values.
• Return the value at mid-1 as the pivot if it exceeds the value at mid.
• Otherwise, return the mid-value as the pivot if the value at the mid+1 is smaller than the mid.
• Consider the left half instead if the value at the low position is higher than the value at the mid position. If not, think about the right half.
• Using the discovered pivot as a guide, divide the array into two smaller arrays.
• One of the two sub-arrays should now be called using binary search.
• Search in the left array if the element is greater than the 0th element.
• If not, look in the appropriate array.
• Return the index if the element can be found in the chosen sub-array.
• Return -1 if not.

Example:

#include <bits/stdc++.h>
using namespace std;
// Standard Binary Search function
int binarySearch(int arr[], int low, int high, int key)
{
    if (high < low)
        return -1;


    int mid = (low + high) / 2;
    if (key == arr[mid])
        return mid;


    if (key > arr[mid])
        return binarySearch(arr, (mid + 1), high, key);


    return binarySearch(arr, low, (mid - 1), key);
}
int findPivot(int arr[], int low, int high)
{
    // Base cases
    if (high < low)
        return -1;
    if (high == low)
        return low;


    int mid = (low + high) / 2;
    if (mid < high && arr[mid] > arr[mid + 1])
        return mid;


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


    if (arr[low] >= arr[mid])
        return findPivot(arr, low, mid - 1);


    return findPivot(arr, mid + 1, high);
}


int pivotedBinarySearch(int arr[], int n, int key)
{
    int pivot = findPivot(arr, 0, n - 1);


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


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


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


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


// Driver program to check above functions
int main()
{


    int arr1[] = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int key = 3;


    cout << "Index of the element is : "
<< pivotedBinarySearch(arr1, n, key);


    return 0;
}

Output:

Index of the element is : 8

Time complexity of the following program is - O(log N)

The Space complexity of the following program is - O(1)