In this post, we will talk about rotated array binary search problem. Three major things are discussed: First of all, instead of providing the solution, we’ll cover how to analyze the question and how to come up with the right idea. Second, it’s not easy to write the bug-free solution for this problem and we’ll talk about some tips and hacks. Last, like our other posts, common techniques are summarized at the end of the post so that you can use similar tools to solve other coding interview questions.
Why we select this question?
I know you are extremely busy with interview preparation and you should be very clear why you need to practice with this question. If this doesn’t work for you, don’t waste your time. And I want you to be selective to every question you practice.
Three reasons I want to cover this problem:
- The question has recently been asked by Airbnb and several other companies, and many people are still confused about it.
- It’s a great question to test your understanding of time complexity and search algorithm.
- I put the most important reason at the last – it’s hard to write the bug-free solution and so many people failed to complete the code although they could easily come up with the right idea.
Rotated Array Binary Search
Search an element in a sorted and rotated array.
If you haven’t practiced with this problem before, please spend some time thinking about it. The post will be much more valuable if you first solve the problem by yourself.
Here we go.
As an interviewer, the first thing I want a candidate to come up with is not actually the final solution. Instead, it’s recommended to clarify the question if anything is unclear. In this specific problem, I hope you will ask whether there are duplicates in the array. It’s okay if you don’t come up with at the beginning, but you’d better clarify this at some point in the interview.
Let’s assume there’re no duplicates in the array for simplicity. The obvious solution is to go over the array and check each of the number, which gives us O(N) time complexity and O(1) space complexity.
So how could you know this is not the optimal solution? It’s not because it’s too easy to come up with. But not only have you not used the condition that the array is rotated and sorted, you also know that some algorithm like binary search can have O(logN) complexity.
Two hints here should lead you to binary search. First, the array is sorted. Second, you already have O(N) solution and want to make it faster – maybe O(logN). Now it’s time to test your understanding of binary search. Basically, if you truly understand fundamentals of binary search, the problem should be very simple.
Binary search is not about sorted array or recursion, which are all very superficial. The essence of binary search is to reduce time complexity by eliminating half of the candidates. If you can apply the same principle, you will achieve faster algorithm.
So coming back to the problem. One straightforward idea is to first find the pivot number. Once we get it with O(logN) complexity, we can apply two binary searches in the left and right subarrays and the overall time complexity is still O(logN). To locate the pivot point, we first check the middle element of the array A[mid]:
- If the middle element is smaller than the two numbers next to it, it is the pivot number.
- If the middle element is larger than both the first and last element, the pivot number is at the right half the array.
- If the middle element is smaller than both the first and last element, the pivot number is at the left half the array.
Can we make it even faster?
One direction is to make it O(1) time complexity, which seems hard. Another way to think about this is that the above solution is 3 * logN since it needs one pass for finding the pivot number and another two passes for two binary searches. So we can try to make it logN, which is still better.
If we want to make it logN, the question actually is whether we can eliminate half of the candidates easily. Similar to binary search, when checking the middle element, can we tell if the target number is on the left or right half array?
Let’s see these examples. Given the following array, suppose our target number is 8. When checking the middle element 3, first we know that the pivot point is at the left of 3. In other words, everything after 3 is well sorted. Therefore, if the target number is in the range of [3, 9], it must be in the right half of the array. For target 8, we can only focus on the right half.
And we can summarize the algorithm as follows:
- If the middle element is the target number, just return.
- If the pivot point is at the left of the middle element:
- If the target is in the range of [mid, rightmost element], then it’s in the right half of the array.
- Otherwise, it’s in the left half of the array.
- If the pivot point is at the right of the middle element:
- If the target is in the range of [leftmost element, mid], then it’s in the left half of the array.
- Otherwise, it’s in the right half of the array.
Code is the hardest part
As you may already know, only 10% of programmers can write bug free binary search. It’s not easy to make your code pass all test cases for this question. I’ll share some tips to help you avoid common pitfalls. In general, we can define a function like Search(array, left, right, target) where we use left and right to keep the indices of the array to search for. Each time, we remove half of the array and recursively search from the rest.
Since the solution is recursive, the first thing to consider is when should we stop the recursion. For this question, we should stop when the left and right pointer is same or left is larger than right. More importantly, don’t forget to check if the middle element is the target, which also allows us to stop immediately.
Avoid infinite loop
One common mistake of recursive solutions is that your program ends up running forever. One great way to avoid this is to make sure your subproblem is strictly smaller than the overall problem. For this problem, when you search thru the right half, instead of doing Search(array, mid, right, target), use Search(array, mid + 1, right, target). This guarantees that the subarray (mid+1 to right) is always strictly smaller than the whole array. For instance, the former solution will fail when you search 1 from array [2, 5] since mid is same as left in this case.
Check all corner cases
It’s really hard to get your solution perfect the first time. You always need to test it. This is also true in a real interview. When you finish your code, validate with several test cases manually. In fact, if the candidate didn’t do this, I’ll ask him to do as an interviewer.
For this question, you should come up with the following corner cases:
- Empty array
- Array with 2 elements
- Middle element is the pivot number
- Target is not present
Here comes the full solution:
Let’s summarize some commonly used techniques from rotated array binary search problem that you can reuse in other problems.
- The essence of binary search is to reduce time complexity by eliminating half of the candidates.
- If you are not sure about those conditions, try with few actual examples like how we analyzed in the post.
- It’s worth to read again “code is the hardest part” section. You should be very clear about how to write bug free recursion after this post.
- What if the array contains duplicates, think about it.