Search An Element In A Sorted And Rotated Array

Problem Statement:

You are given a sorted and rotated array your work is to find the given element in the array.

Hint:

For finding the given element in the given array we can make use of the binary search which can be applied in the sorted array which may be a fully sorted array or a partially sorted array. We can divide the array into two parts recursively each time while finding the pivot element or the mid element and check for the given element.

Quick Think:

For designing the algorithm for the above problem statement we have to keep the following points in our mind:-

• The first condition to be check should be that the pivot element of the array is greater than or equal to the first element in the given array.
• Next approach should be dividing the array into two parts based on where the given element lies.
• Now if the first part of the array is not sorted then the second part must be sorted and hence, a similar condition has to be applied to the second part.

Algorithm:

The algorithm for the above implementation will be by creating a function which will take the arguments as the array, with the start and the end index of the array and the element to be searched and follow the following steps:-

Step1: Check for the condition that the first index of the array is not greater than the final index of the array if not go to step 2 else return -1.

Step2: Now, find the pivot index of the sorted and rotated array and then go to step 3.

Step3: If the pivot element is equal to the given element then return the element else goto step 4.

Step4: Check for the condition that the first element in the array is less than or greater then the pivot index element if yes then goto step 4 else go to step 5.

Step5: Now check for the condition that if the given element to be searched is between the first and the mid index of the given array if yes then recursively call the function with the arguments as given array, the first index, the pivot index’s previous index and the given array element else go to next step 6.

Step6: Now, if the given element is not present in the given array then it must be present in the second part of the array so again, recursively call the function with the arguments as the given array, the pivot index’s next index and the final index of the array and the given element to be searched.

Step7: Now, if the first part of the array is not sorted then, the second part of the array must be sorted so, we look for the element in the second part of the array and if the given element to be searched is between the pivot index element and the last index element in the array then the function is recursively called with arguments as the given array, the pivot index’s next index and the final index of the array and the given element to be searched else go to step 8.

Step8: Finally if step 6 does not work then, the function is recursively called with arguments as the given array, the pivot index’s previous index and the final index of the array and the given element to be searched.

Implementation Of The Above Algorithm:

#include <bits/stdc++.h>
using namespace std;
/*Function to search for the given element by using binary search. */
int searchmid(int arr[], int start, int end, int key)
{
	if (start > end)
		return -1;
	/*Calculate pivot. */
	int pivot = start + (end - start) / 2;
	/*If pivot is equal to the given element then return the index of the element. */
	if (arr[pivot] == key)
		return pivot;
	/*If first part of the array is sorted. */
	if (arr[start] <= arr[pivot])
	{
		if (key >= arr[start] && key <= arr[pivot])
			return searchmid(arr, start, pivot - 1, key);
		return searchmid(arr, pivot + 1, end, key);
	}

	/*Else the second part of the array is sorted. */
	if (key >= arr[pivot] && key <= arr[end])
		return searchmid(arr, pivot + 1, end, key);
	return searchmid(arr, start, pivot - 1, key);
}

// Driver program
int main()
{
	int arr[] = { 4, 5, 6, 7, 8, 9, 1, 2, 3 };

	int n = sizeof(arr) / sizeof(arr[0]);
	int key = 6;
	int i = searchmid(arr, 0, n - 1, key);

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

Running Time Complexity Of The Above Algorithm is- O(logn).

Output Of The Above Algorithm is- 2.

Explanation Of The Above Algorithm:

Let us consider the example of the array as given in the above algorithm as shown in the diagram above and follow the following steps to reach the final output:-

• Since the first index is smaller than the last index hence the pivot index comes out to be four, which points to the element 8 in the given array as shown in the above diagram.

• Now, the given element to be searched is 6 suppose, so we see that the given element lies between the first index and the index of the pivot element previous index i.e. 7 so, we will consider the subarray as shown in the diagram above.

• Again we see that the index of the first element is less than that of the last element, so we calculate the pivot index of the subarray so formed, and the pivot index comes to be 5 as shown in the diagram above.

• But, here now we see that the given element is present in the next subarray as shown in the above diagram.

• Again, we see that the index of the first element is not greater than the index of the last element and hence, we will calculate the pivot index which comes out to be 6 as shown in the above diagram.

• Now, since the pivot element is the given element to be searched itself hence, we return the pivot element and hence, obtain our output as shown in the above diagram and we will print the index of the above output which is equal to 2.