Home » Data Structure » Array Data Structure

Search an element in a sorted and rotated array

Last Updated : April 19, 2025

Consider an integer array of size n that is sorted in ascending order and then rotated using a pivot value which is unknown. Now if the array is just sorted, we can search an element using binary search with a time complexity of O(log(n)). But since the array is rotated, frame a solution to find an element in the given array in O(log(n)) time.

Example:

Input:
array[]= {5, 1, 2, 3, 4}
element = 1

Output:
Element is present at index: 4

Input:
array[]= {50, 10, 20, 30, 40}
element = 5

Output:
Element is not present

Search an element in a sorted and rotated array using find pivot value and search

This is a simple approach that involves finding the pivot element in the given array. The pivot element is the one that has a value greater than its next element. After finding it we can split the array into two parts and perform a binary search on them individually to find the desired element. It involves the following steps:

• Iterate through the array
• Find the pivot element by checking whether the element is greater than its following element
• Divide the array at the pivot value into two groups
• Call either of the two groups for binary search by checking the group's first element with the element to be searched
• If found, print the element's index

C++ Implementation

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

// Function to perform binary search
int binarySearch(int array[], int low, int high, int element)
{
    if (high < low)
        return -1;

    int mid = (low + high) / 2;
    if (element == array[mid])
        return mid;

    if (element > array[mid])
        return binarySearch(array, (mid + 1), high, element);

    return binarySearch(array, low, (mid - 1), element);
}

// Function to find the pivot element
int findPivot(int array[], int low, int high)
{
    // base cases
    if (high < low)
        return -1;
    if (high == low)
        return low;

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

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

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

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

// Function to search an element
// In sorted and rotated array
int searchElement(int array[], int length, int element)
{
    int pivot = findPivot(array, 0, length - 1);

    // If the array is not rotated
    if (pivot == -1)
        return binarySearch(array, 0, length - 1, element);

    // if element at pivot is the element to be search
    if (array[pivot] == element)
        return pivot;

    if (array[0] <= element)
        return binarySearch(array, 0, pivot - 1, element);

    return binarySearch(array, pivot + 1, length - 1, element);
}

// Main function
int main()
{
    int array[100], N, element;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }
    cout << "Enter the element to be searched: ";
    cin >> element;

    int index = searchElement(array, N, element);
    if (index == -1) {
        cout << "Element is not present";
    }
    else {
        cout << "Element is present at index: " << index;
    }

    return 0;
}

Output:

Enter Number of elements: 6
Enter element 1:4
Enter element 2:5
Enter element 3:6
Enter element 4:1
Enter element 5:2
Enter element 6:3
Enter the element to be searched: 2
Element is present at index: 4

Time Complexity: O(log(n)), where n is the length of the array.

Search an element in a sorted and rotated array using modified binary search

This is an updated method from the previous solution and it does not require finding the pivot element. It involves the following steps:

• Assign low=0 and high=n-1
• Find mid=(low+high)/2
• Check if array[mid] is the element to be search, if yes, return mid
• Else if, check array[low..mid] is sorted. If yes, recursively call array[low..mid] if element lies in array[low..mid]. If not, recursively call array[mid+1..high]
• Else, the array[mid+1..high] should be sorted. Check element lies in array[mid+1..high]. If yes, recursively call array[mid+1..high], else recursively call array[low..mid]
• Print the element's index

C++ Implementation

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

int search(int array[], int low, int high, int element)
{
    if (low > high)
        return -1;

    int mid = (low + high) / 2;
    if (array[mid] == element)
        return mid;

    // If array[low..mid] is sorted
    if (array[low] <= array[mid]) {

        // check the whether element lies in first half
        if (element >= array[low] && element <= array[mid])
            return search(array, low, mid - 1, element);

        return search(array, mid + 1, high, element);
    }

    // array[mid+1..high] will be sorted
    if (element >= array[mid] && element <= array[high])
        return search(array, mid + 1, high, element);

    return search(array, low, mid - 1, element);
}

// Main function
int main()
{
    int array[100], N, element;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }
    cout << "Enter the element to be searched: ";
    cin >> element;

    int index = search(array, 0, N - 1, element);
    if (index == -1) {
        cout << "Element is not present";
    }
    else {
        cout << "Element is present at index: " << index;
    }

    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1:4
Enter element 2:5
Enter element 3:1
Enter element 4:2
Enter element 5:3
Enter the element to be searched: 3
Element is present at index: 4

Time Complexity: O(log(n)), where n is the length of the array.