Problem 🤔

Given the following:

• an array with n integers
• sorted in increasing order
• that has been rotated an unknown number of times

Implement a function to find an element in the list.

Example 1

Input: target = 5, arr =[15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14]

Ouput: 8, the index of 5 in the array

Real World Applications 🌎

Aren’t we all always on a rotating schedule?

The Finer Details 🔎

Okay so the naive solution here is straight forward. Let’s scan the list one and look for our target. I’ll humor ya’ll w/ the code:

Cool? It’s alright for a start. We haven’t taken advantage of the fact the list is nearly sorted!

Solution 💡

If this list was completely sorted we could use vanilla binary search. Since the list has been rotated once we’ll need to do a little extra work here.

So, let’s break this down into two steps.

1) We’ll find the rotation point. We can do this with an adjusted binary search! The simplest way to think about this is as follows: How will we know if an array isn’t sorted? We can look at the first and last element. If the last element is not larger than the first we know it’s not sorted!

2) Once we find the rotation point we essentially have 2 sorted arrays! We know the range of each list, so we can simply search the array that contains our target.

Complexity Analysis 🧮

Time Complexity

Run time: O(log(n))

We’re running binary search twice.

Space Complexity

O(1)

No auxillary variables allocated.

Takeaways 🎉🥳

• A great takeaway from this problem is that we can modify binary search for our needs! We just need to adjust the search termination condition.
• This is only 1 example of such a modification. Can you think of more?

Resources 📚

Leetcode

• Cracking the Coding Interview, 10.3 Search in Rotated Array