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, in turn, help you crack a number of complex problems — searching an element in a sorted and rotated array.

We solve it using “single-pass binary search by comparing mid and target elements.” **This is approach 4 of 4.**

To check out the other approaches, follow the links:

- Approach 1) Linear search
- Approach 2) Two-pass binary search
- Approach 3) Single-pass binary search using casework

**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 1,Approach 2,andApproach 3to understand the coverage better.

The graph of the input array looks something like the below graph:

In the following image, we have simplified the graph. We’ve modified the two curved poly-lines to straight lines by joining the first and last points. Also, we’ve colored the points on the left poly-line green and the points on the other poly-line red.

**Key observation: **Suppose our search space is bounded by [left, right], and *mid *is the middle element of the search space. Initially, we will start with a search space that will span the whole array. Then, in each iteration, we reduce the size of the search space in half. We can decide which half to discard by checking if both arr[mid] and target lie on the same part in the image above.**How to discard the range/move pointers:**

There are two cases to consider here — one where both mid and target are on the same part, and the second where they’re on different parts. **How will we check this? **We will compare arr[mid] with arr[0] and do the same for the target. If both target and arr[mid] are greater/lesser than arr[0], then it shows that they lie on the same part, else they lie on different parts.

**Case 1: **Both mid and target lie on the same part.

In the image above, we can see that *mid *and *target *lie on the same part. So, we can search the range marked in red.

**Case 2:** When mid and target lie on different parts.

We’ll use a trick here — we’ll extend the line of the left part to infinity and the line of the right part to -infinity.

In the above case, to move *left *and *right, *we need to compare arr[mid] with the target. However, as they are on different sides, we use a comparator in place of arr[mid], as we just need a value with which we can move our left and right pointers.

So, we will compare the target with arr[0]. Here, targets lie below arr[0], i.e., arr[0] > target. We will set *comparator *= -INFINITE. **Why? **Because we need to go to the right side and to do that, we must compare *target *with a value *smaller than the target*. (The same logic is used in standard binary search.)

Now, we compare *target *and *comparator. *As target > comparator, we move towards the right and set *left = left + 1.*

Else, if *comparator > target, *we would move towards the left set *right = mid - 1*.

Now, let's consider a scenario where the target lies on the left and mid lies on the right side.

In this case, we need to set the *comparator *to INFINITE. **Why? **Because our target element lies on the left side, and to move *left, *we need to compare the target with a value greater than the target.

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

**2. **Run a loop until left <= right:

** a. **Calculate "mid" as mid = (left + right) / 2.

** b. **If (arr[0] > arr[mid]) == (arr[0] > target), then this shows arr[mid] and target lie on the same side with respect to target. so set "comparator" = arr[mid].

** c. **Else:

** i. **If target < arr[0], then set "comparator" to -INFINITY

** ii. **Else, set "comparator" to INFINITY

** d.** If comparator == target, then return mid as we found our target element.

**e.** If target < comparator, then search target in [left, mid) and move "right" pointer as right = mid - 1.

** f. **Else, search target in (mid, right] and move left pointer as "left" = mid + 1.

**3. **Return -1 as we are not able to find the target in our array arr.

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

#include<bits/stdc++.h>

using namespace std;

// Function to search target in array 'arr'

int searchInRotatedSortedArray(int arr[], int n, int target)

{

int left = 0, right = n - 1;

while (left <= right) {

int mid = (left + right) / 2;

int comparator;

// Check if arr[mid] and target lies on same side

if ((arr[0] > arr[mid]) == (arr[0] > target))

{

comparator = arr[mid];

}

else

{

// Target lies on the right part

if (target < arr[0])

{

comparator = INT_MIN;

}

// Target lies on the left part

else

{

comparator = INT_MAX;

}

}

// We have found our target

if (comparator == target)

{

return mid;

}

// Target lies on [left, mid)

if (comparator > 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;

}

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;

}

**O(log(N))**, where "N" is the total number of elements in the given array.

Similar to Approach 3, we are reducing our search space by half at each step. We get recurrence as T(N) = T(N / 2) + C, where C is Constant.

**Best Case: O(1)**Happens when the comparator equals the target for the first value of mid.

**Worst Case: O(log(N))**Happens when the target is not present in the array.

**Average case: O(log(N))**Happens when the target is present in the array. We need to do log(N) steps on average to find the target.

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

**Question 1: Which is the best approach for searching an element in a sorted and rotated array?**

Answer: For searching an element in a sorted and rotated array, using single-pass binary search is better than using linear search or two-pass binary search. There are two ways of doing this: Single-pass Binary Search Using Casework and Single-pass Binary Search by Comparing Mid and Target Elements (which we covered in this post).

**Question 2: Would the same solution work if the array had duplicates? **

Answer: If we had equal numbers, we might not always be able to decide whether we need to move towards the left or right in our binary search algorithm. So, the same solution will not work in that case.

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