Search in a Rotated Sorted Array

This article helps one understand — Binary Search and some tricks. We start by looking at the vanilla Binary Search algorithm and then move on to discuss some tweaked versions of Binary Search. For full blown solutions to these problems you can always refer LeetCode. This article intends to just “Spot the Differences”. 🤓😎

Problem 1

Suppose an array is sorted in ascending order and you are given a target value to search. If found in the array return its index, otherwise return -1.

Pretty simple, right?

Approach 1: Linear Search

A Brute approach would be to search for the element in a linear fashion. When there is no better way to search, linear is always a way. This means in the worst case you have to iterate the entire array. While this is one approach you might be using in your day-to-day life but think of what better can you do? After all you have a sorted array. 🤔

Linear is all about iterating the array and stopping when you have found the target element !

Approach 2: Binary Search

This approach is such a subtle algorithm. I am always mesmerized by how such a simple algorithm/concept could be so useful. Look at how drastically it brings down the time complexity of searching an element.

Binary Search comes with a precondition that the array must be sorted.

While Linear Search has a complexity of O(N), Binary Search reduces it to O(logN). Isn’t that amazing? This is because at every step Binary Search just reduces the search space to half.

If you want to read more on binary search you can also checkout my other article, but first let’s end what we started.

A twisted tale of Binary Search

Problem 2

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. You are given a target value to search. If found in the array return its index, otherwise return -1.

Search in Rotated Sorted Array - LeetCode

This problem is similar to Problem 1 in the sense that we have to search for an element in the array. But, we now do not have a sorted array. Since, the array got rotated.

Approach 1: Linear Search

Linear Search is always a savior if nothing else works. It is sweet and simple.
It has its own cons, for instance it might not be the best algorithm when you have millions of records to search from. But that’s not what we are dealing with right now. What we are dealing with is a trick question and we need to handle it with a trick. 🙌

Approach 2: Binary Search

Let me reiterate what I said earlier. The precondition for Binary Search is that it needs a sorted array. But, the input array is not sorted anymore or is it?

Rotated sorted array still maintains the sorting but in two parts. Note, the rotation causes some of the starting smaller elements to move to the back of the array but their relative order is maintained.

In this rotated sorted array we would first need to find out the point/index which divides the array into two parts such that we have two sorted arrays and then decide which part does target belongs to.

For e.g. in the above diagram if we are searching for target = 6 then first part of the array is where we need to search by using Binary Search.

The point which divides the array into two parts can be seen as a point of change, hence let’s call this point as inflection point.

Notice, how the values take a sudden dip before they start to rise again. Thus, let’s call this point as inflection point

Finding inflection point can be done linearly i.e. it would be the point where we would get a sudden dip in the value. But this would also mean we spend O(N) time finding the inflection point and rest of the O(logN) time would be spent for the binary search. What’s the point ? 💁🏻

Rather, can we somehow combine the two steps?

Yes, we can. We can modify the binary search condition to consider the inflection point condition.

This is an important condition since this would help us decide which part the target element would belong to. But this alone won’t solve the purpose. Why?

If A[i] > A[0] then A[i] is to the left of inflection point, otherwise A[i] is to the right of inflection point.

But where is the target. We do not know anything about the target yet.

The target element is to the right of the inflection point, but the middle pointer is still to left of the inflection point. Hence we should go to the right and repeat to find the target.

Let’s see what changes in the binary search conditions.

Look at how both the algorithms even though have the same complexity behave differently as per the conditions. The main difference here is that we first need to find out where the middle element is relative to the inflection point and then find out where is the target element relative to the middle element. When both the middle element and the target element are compared to the common element i.e. the first element in the array we can find out which way to go.

Problem 3

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element.

Find Minimum in Rotated Sorted Array - LeetCode

This problem has such stark similarity to Problem 2. The only difference being the condition around the element we are searching for. While Problem 2 deals with searching for a given target element, Problem 3 just says find the minimum.

Approach 1: Linear Approach

The most basic approach would be to iterate all the elements in the array while keeping a record of the smallest element encountered.

Approach 2: Binary Search

Yes! Even this problem has a solution with Binary Search. After all the array in this problem is also a rotated sorted array and hence we know we can fit binary search here 😜 It’s in fact very similar to the approach we took for Problem 2 with some minute and important differences. Let’s look at the inflection point graph once again.

Look how at the inflection point the values of the array take a sudden dip. The dip is because the first element of the originally sorted array is sitting right here and this is the minimum element in the array.

From the above diagram it’s clear for us to find the minimum element we need to find the inflection point.

Let’s look at the difference between the conditions for Binary Search for Problem 2 vs Problem 3.

This problem definitely doesn’t need an extra check on the target element. Since here the target element is the one next to the inflection point. Thus, what we need to look for is just the inflection point.

Problem 2 had a given target element, hence we had used some additional conditions to find out where target is w.r.t the inflection point and the middle element.
Problem 3 deals with finding the minimum element which is the element next to the inflection point. Thus, for this problem we just need to find out where are we w.r.t the inflection point and then move closer to the inflection point at each step.

Share your views in the comment section. If you have any suggestions for other spot-the-difference problems please share.
Hit the clap 👏 button if you liked the article. 💛