Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Searching an Element in a Sorted and Rotated Array: Two-pass Binary Search

Last updated by Abhinav Rawat on Sep 25, 2024 at 11:01 PM | Reading time: 9 minutes

The fast well prepared banner

Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

How To Nail Your Next Tech Interview

Searching an Element in a Sorted and Rotated Array: Two-pass Binary Search
Hosted By
Ryan Valles
Founder, Interview Kickstart
strategy
Our tried & tested strategy for cracking interviews
prepare list
How FAANG hiring process works
hiring process
The 4 areas you must prepare for
hiring managers
How you can accelerate your learnings

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: 

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

(For simplicity, the two curved poly-lines are modified to be straight lines by joining the first and last point)

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

Last updated on: 
October 10, 2024
Author

Abhinav Rawat

Product Manager @ Interview Kickstart | Ex-upGrad | BITS Pilani. Working with hiring managers from top companies like Meta, Apple, Google, Amazon etc to build structured interview process BootCamps across domains

Attend our Free Webinar on How to Nail Your Next Technical Interview

Register for our webinar

How to Nail your next Technical Interview

1
Enter details
2
Select webinar slot
First Name Required*
Last Name Required*
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

Searching an Element in a Sorted and Rotated Array: Two-pass Binary Search

Worried About Failing Tech Interviews?

Attend our webinar on
"How to nail your next tech interview" and learn

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Our tried & tested strategy for cracking interviews
blue tick
How FAANG hiring process works
blue tick
The 4 areas you must prepare for
blue tick
How you can accelerate your learnings
Register for Webinar
entroll-image