# 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.