Search element in rotated sorted array

In this article, we have explored how to search an element in a Rotated Sorted Array efficiently in O(logN) time with constant space O(1).

Table of contents:

1. Understanding the problem statement
2. Efficient Solution
3. Time and Space Complexity

Prerequisite: Binary Search, Linear Search

Understanding the problem statement

An array is a collection of items stored at contiguous memory locations. The idea is to store various or multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).The base value is index 0 and the difference between the two indexes is the offset.

For clear understanding, we can think of an array as a fleet of stairs where on each step is placed a value(suppose your partners). Here, you can identify the location of any of your partner by simply knowing the count of the step they are on. We can access any element in an array by just knowing its index. There are so many variety of operations we can perform on an array like insertion,deletion,searching,sorting etc.

Let's take an example of an array of different data types:

//integer array in C/C++
int arr[]={1,2,3,4,5}

//character array in C/C++
char ar[]={'a','b','c'}

As we can see that each element can be uniquely identified by its index in the array as arr[0]=1,arr[1]=2,arr[2]=3,arr[3]=4,arr[4]=5 and ar[0]=a,ar[1]=b,ar[2]=c where in arr[0] [0] is an index to access a particular element. Here we are using zero based indexing(zero based indexing is a type of indexing in which first element of an array is indexed by a subscript of 0). There are also one based indexing(one based indexing is a type of indexing in which first element of an array is indexed by a subscript of 1) and n based indexing(n based indexing is the one in which base index of an array can be freely chosen).

Now before moving towards our problem first let's understand what is a rotated sorted array. A rotated sorted array means it is an array which is at first sorted(sorted array means an array in which all its elements are arranged in ascending or descending order) but if we rotate its elements from some index either towards left or towards right,then that final array becomes a rotated sorted array.
For instance, suppose you have a sorted array containing elements {1,2,3,4,5} now if you rotate this array from index 1(zero based indexing) so it will become {3,4,5,1,2}. Now i am sure you will have a good understanding of what is a rotated sorted array.

Moving further, first let's see what our question? We have to search for an element in a rotated sorted array. First we have to understand how to search an element in a given array. There are two algorithms which help us in performing search operation in an array. They are:

1. Linear search
2. Binary search

Linear search is a very basic searching algorithm which search an element in O(n) time which is somehow good but we always looks for an efficient and less time consuming algorithm so that our code or program gets executed in small time and there will be no issues. Linear search is not good for a large size array so that's why we prefer using binary search algorithm as it takes only O(log n) time in executing a code which is far better as compared to the linear search time complexity.

So now we know that we have to apply binary search technique to solve this given problem. First understand what is binary search technique and how it works while searching for an element in an array. In binary search we repeatedly keep on dividing the sorted array into two equal halves. At the start we find the middle element in an array and compare that element with the given element which is need to be searched. If that element is equal to the middle element we have successfully searched that element but if that element is smaller than the middle element we start searching that element in the first half of the array as it is sorted and if that element is bigger than the middle element we start searching that element in the second half of the array. By this way we can easily reduce the number of comparisons in each step and finally perform a successful search if that element is present in the array. You will easily understand with the help of an example:
Suppose we have an array:

int a[]={1,2,3,4,5}

and our target value(which is to be searched) is 2
We find the middle element that is 3(bolder) now compare 3 with the target value i.e, 2 we can see that 3>2 so we as the array is sorted all the values smaller than 3 will be on the left side of 3 i.e, in the left half of the array which contains element 1,2 and now we can easily compare and search for the given target value applying the same procedure as we have applied above(taking the middle element and compare it with target value).

Implementation:

1. Compare target with the middle element.
2. If target matches with the middle element, we return the mid index.
3. Else If target is greater than the mid element, then target can only lie in the right half subarray after the mid element. So we recur for the right half.
4. Else (target is smaller) recur for the left half.

After seeing the approach we will write a C++ code for this technique.

// C++ program to implement Binary Search
#include <bits/stdc++.h>
using namespace std;

// A iterative binary search function. It returns
// location of x in given array arr[low..high] if present,
// otherwise -1
int binSearch(int a[], int low, int high, int target)
{
	while (low <= high) {
		int mid = low + (high - low) / 2;   //finding the middle element

		// Check if target is present at mid
		if (a[mid] == target)
			return mid;

		// If target greater, ignore left half
		if (a[mid] < target)
			low = mid + 1;

		// If target is smaller, ignore right half
		else
			high = mid - 1;
	}

	// if we reach here, then element was
	// not present
	return -1;
}

int main()
{
	int arr[] = {1,2,3,4,5};
	int x = 2;
	int n = sizeof(arr) / sizeof(arr[0]);
	int ans = binSearch(arr, 0, n - 1, x);
	if(ans==-1){
      cout<<"Element is not present"<<'\n';
	}
	else{
	    cout<<"Element is present at index"<<" "<<ans<<'\n';
	}
	return 0;
}

Output:

Element is present at index 1

Efficient Solution

Now after seeing binary search we can proceed towards our given problem. We know that an element can be searched in a sorted array using binary search in O(log n) time. In our problem we are given a rotated sorted array and we have to search for that particular element in the array.

We know that the array which is sorted is rotated from some index which is unknown so if we can find that element(let's say this element as pivot element) which is present at that index we can easily apply binary search as the elements in the left side and right side of that pivot element will be already sorted.First we will see the basic approach then its proper implementation and finally with the help of all these we will write a code for this problem.

Basic approach:

1. The idea is to find the pivot point, divide the array in two sub-arrays and perform binary search.
2. The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only element for which next element to it is smaller than it.
3. Using the above statement and binary search, pivot element can be found.
4. After the pivot element is found out, divide the array in two sub-arrays.
5. Now the individual sub – arrays are sorted so the element can be searched using binary Search.

Implementation:

Suppose we have an array arr[] = {3, 4, 5, 1, 2}
Element to Search = 1

1. Find out pivot element and divide the array in two
   sub-arrays. (pivot = 2) //Index of 5
2. Now call binary search for one of the two sub-arrays.
   (a) If element is greater than 0th element then
   search in left array
   (b) Else Search in right array
   (1 will go in right subarray(right half) as 1 < 0th element(3))
3. If element is found in selected sub-array then return index
   Else return -1.

For better clarity we will take an example and understand step by step that what is happening.

Example : Suppose we have an array arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3} and we have to search for 3 in this rotated sorted array so how to do?
First we will find the pivot point(that point at which all elements on its left side and right side are sorted in correct order), we can see that pivot element is 10(bolder) now we will compare our target value with the first element of this array i.e, 5. As we can see that 5 > 3(target value) so now we have to search for this element in the right side of pivot having elements as 1,2,3. Now we have a sorted array we can easily apply binary search by finding middle element i.e, 2(bolder) and comparing it with 3(target value) we can see that 3>2 so it will be present in the right side of the middle element and we have successfully searched for our target value.

C++ implementation:

//C++ Program to search an element in a sorted and rotated array/
#include <bits/stdc++.h>
using namespace std;

//Standard Binary Search function
int binSearch(int a[], int low, int high, int target)
{
	if (high < low)
		return -1;

	int mid = (low + high) / 2;  //finding middle element
	if (target == a[mid])
		return mid;

	if (target > a[mid])
		low = mid + 1;

	else
        high = mid - 1;
}

//Function to get pivot
int findPivot(int a[], int low, int high)
{
	// base cases
	if (high < low)
		return -1;
	if (high == low)
		return low;

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

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

	if (a[low] >= a[mid])
		high = mid - 1;

	else
        low = mid + 1;
}

//function for searching the target element
int pivotedBinarySearch(int a[], int num, int target)
{
	int pivot = findPivot(a, 0, num - 1);  //function calling

	// If we didn't find a pivot,
	// then array is not rotated at all
	if (pivot == -1)
		return binSearch(a, 0, num - 1, target);

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

	if (a[0] <= target)
		return binSearch(a, 0, pivot - 1, target);

	return binSearch(a, pivot + 1, num - 1, target);
}

int main()
{
	int a[] = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
	int num = sizeof(a) / sizeof(a[0]);
	int target = 3;

	// Function calling
	cout << "Index of the element is : "<< pivotedBinarySearch(a, num, target);
	return 0;
}

Output:

Index of the element is : 8

Time and Space Complexity

1. Time complexity: O(log n) as we are using binary search which uses log n comparisons to search an element where n is the size of the array.
2. Space complexity: O(1) constant space as no extra memory or space is required.

If we have an array which contain duplicate elements it is not possible to search in O(log n) time in all cases. For example consider searching 0 in {3,3,3,3,3,3,0,3,3} and {3,3,0,3,3,3,3,3,3}. It's not possible to decide whether to recur for the left half or right half by doing a constant number of comparisons at the middle.

So now I am sure you all have a clear understanding of how to approach and solve this problem. Try it by yourself and keep coding. This problem is similar to Leetcode problem 33. Search in Rotated Sorted Array.

Thank you.