Home » Data Structure » Array Data Structure

Search an element in a sorted and rotated array

C++ implementation to search an element in a sorted and rotated array.
Submitted by Vikneshwar GK, on February 18, 2022

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

Solution 1: 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.

Solution 2: 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.