For software engineers, preparing for a tech interview means a lot of practice! Not only must you practice several problems, but you also need to ensure that you cover a wide variety of topics. 

In this article, we’re going to tackle a problem on search, which will help you crack a number of complex problems — searching an element in a sorted and rotated array.

We solve it using “two-pass binary search.” This is approach 2 of 4.
To check out the other approaches, follow the links: 

• Approach 1) Linear search
• Approach 3) Single-pass binary search using casework
• Approach 4) Single-pass binary search by comparing mid and target elements
  

Here, we cover:

• Problem statement
• Approach explanation
• Algorithm for the approach
• Code for the approach
• Time complexity of the approach
• Space complexity of the approach

Problem Statement

You have been given a sorted and rotated array "arr" of "N" distinct integers. You are also given an integer "target." Your task is to print the index of the integer "target" in array "arr." If "target" does not exist in "arr," then you need to print -1.

Note:

• "arr" contains distinct elements. This means that there is NO pair of indices (i, j) such that 0 <= i < j < N and arr[i] equals arr[j].
• "arr" is a rotated sorted array. 
  

The following array adheres to all the above conditions:

Now, if we rotate it three times towards the right, we get a sorted and rotated array:

Let’s take a couple of input examples:

Input 1: arr = [9, 11, 1, 3, 5 ,7] and target = 5
‍Output 1: 4
Explanation 1: 5 is present at index 4, so we need to print 4.

Input 2: arr = [9, 11, 1, 3, 5 ,7] and target = 8
Output 2: -1
Explanation 2: 8 is not present in "arr," so we need to print -1.

Now that we have a clear understanding of our problem, we will move to the solution.

Please make sure you’ve read Approach 1 to understand the coverage better.

Approach 2: Two-pass Binary Search

Find the minimum element of the array, then apply binary search on the divided parts separately. The critical observation here is — the graph of the input array looks something like the below graph:

The graph is first increasing, and then we can see a drastic decrease. So, if we can somehow find the “index” of the minimum number in the array, we can apply binary search on the red and green colored lines as shown in the figure below (as they are strictly increasing).

Now, how will we divide our array into red and green parts? In other words, how can we find the index of the smallest number? We’ll use binary search. You may have the questions:

1. How will we reduce our search space? We will reduce our search space by comparing arr[right] with arr[mid]. Here, “left” and “right” are pointers, and they point to the two ends of our search space, and “mid” points to the element at the middle.
   
   
2. Binary search is applied to increasing/monotonic function. Is there any increasing function that exists here? Yes, there exists an increasing function. 

Let’s use an example to understand the approach better:

Step 1: Left = 0 | Right = 7 

Calculate mid as mid = (left + right)/2 = (0 + 7)/2 = 3

arr[3] > arr[7], i.e., arr[mid] > arr[right]. Therefore, min elements are on the right side. All elements from [left, mid] are also greater than arr[right], as arr is monotonically increasing in [left, mid].

Now, we need to move our left and right pointers. We can discard the left part and search the range [mid + 1, right]. We’ll make left = mid + 1.

Step 2: Left = 4 | Right = 7

Mid = (4 + 7)/2 = 11/2 = 5

arr[mid] < arr[right]. Hence, min elements lie on the left side. Next, we need to move the left and right pointers. All elements from [mid + 1, right] are greater than arr[mid], as arr is monotonically increasing in [mid + 1, right]. We discard this part and search in [left, mid].

We make right = mid.

Why haven't we made right = mid - 1, or if we do this, will it work?
‍No, it won’t work. Because arr[mid] could be the minimum element, so we can't exclude it.

Step 3: Left = 4 | Right = 5

Mid = (left + right)/2 = (4 + 5)/2 = 9/2 = 4

Now, arr[mid] < arr[right]. So, we set right as right = mid.

Step 4: Left = right, so we stop as we have found the minimum element.

Let's call the min element index "minIndex." We’ll apply standard binary search on [0, minIndex - 1] and [minIndex, right] to search the "target" element. 

Algorithm

1. Declare three variables, left, right and mid, for binary search and initialize left = 0, right = size of array - 1

2. Find minIndex of array:

    a. Run a loop until left < right:

        i. Calculate mid as mid = (left + right)/2

        ii. If arr[mid] > arr[right], then set left as mid + 1

        iii. Else, set right as mid

3. Set "minIndex" as "left"

4. Now, call the binarySearch function and apply it on [0, minIndex - 1] and [minIndex, N - 1] and store the result in the "answer" variable

5. Return "answer"

Code in C++

Following is the implementation of the approach in C++.

/*
    Time Complexity:  O(log(N))
    Space Complexity: O(1)

    Where N is the total number of elements in the given array.
*/

#include<iostream>
using namespace std;

int binarySearch(int arr[], int left, int right, int target)
{

while (left <= right)
{
int mid = (left + right) / 2;

if (arr[mid] == target)
{
return mid;
}

// Target lies on [left, mid)
else if (arr[mid] > target)
{
right = mid - 1;
}

// Target lies on (mid, right]
else
{
left = mid + 1;
}
}

// We are not able to find a target so return -1.
return -1;
}

// Function to search target in array 'arr'
int searchInRotatedSortedArray(int arr[], int n, int target)
{

int left = 0, right = n - 1, mid;

while (left < right)
{
int mid = (left + right) / 2;

// Min index lies in (mid, right]
if (arr[mid] > arr[right])
{
left = mid + 1;
}

// Min index lies in [left, mid]
else
{
right = mid;
}
}

int minIndex = left;
int ans = -1;

// Search target in [0, minIndex)
ans = binarySearch(arr, 0, minIndex - 1, target);

// Search target in [minIndex, N - 1]
if (ans == -1)
{
ans = binarySearch(arr, minIndex, n - 1, target);
}

return ans;
}

int main()
{

      int n = 10;

int arr[n] = {10, 13, 16, 20, 25, 1, 3, 4, 5, 8};

int target = 4;

cout << searchInRotatedSortedArray(arr, n, target);

return 0;
}

Time Complexity

The time complexity is O(log(N)), where "N" is the total number of elements in the given array.
Best Case = worst Case = average case

Let’s see how:

Orange lines denote the previous length/searching space we had.

Green markings denote the part of the line we chose to search, and red lines indicate the mid-value.
You can see at each step we are discarding at least half the length of the array.
So, green = orange/2

Let's say the initial length of our array = N.
At each iteration, the length of the array is reduced by half.
So, we get the recurrence T(N) = T(N / 2) + C
Here, C is some constant. 

After 1st iteration length of array  = N/2
After 2nd iteration length of array = N/4
After 3rd iteration length of array  = N/8
.
.
.
After kth iteration length of array = N/(2^k)

Also, we know that the array’s length will become 1 after k iteration.
Mathematically, ceil(N/(2^k)) = 1 will be true for the last iteration.
N will be close to 2^k.
Hence, K will be of O(log(N)). 

Therefore, the time complexity will be O(log(N)).

Note: Time complexity of binarySearch function:
Best case: O(1)
Worst case: O(log(N))
Average case: O(log(N))

Space Complexity

Best case = worst case = average case = O(1)

We are using a few extra variables that take O(1) space. Hence, the space complexity will be O(1). 

There’s More ...

There’s room to optimize this approach a little more. Read this article to learn more: 

Searching an Element in a Sorted and Rotated Array: Single-pass Binary Search Using Casework

Nervous About Your Next Coding Interview?

Let Interview Kickstart help you! 

As pioneers in the field of technical interview prep, we have trained over 5200 software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

Sign up now!

————

Article contributed by Pankaj Sharma