Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

Interview Kickstart has enabled over 3500 engineers to uplevel.

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

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 readApproach 1to understand the coverage better.

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:

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

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

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

**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"

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;

}

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/2After 2nd iteration length of array = N/4After 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))

**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 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*

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!

————

*Article contributed by Pankaj Sharma*

Attend our webinar on

"How to nail your next tech interview" and learn

Hosted By

Ryan Valles

Founder, Interview Kickstart

Our tried & tested strategy for cracking interviews

The 4 areas you must prepare for

How you can accelerate your learnings