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. 🤔
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.
If you want to read more on binary search you can also checkout my other article, but first let’s end what we started.
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
.
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?
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.
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.
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.
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.
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.
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.
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. 💛