Solution: Search in Rotated Sorted Array

Statement#

Given a sorted integer array, nums, and an integer value, target, the array is rotated by some arbitrary number. Search and return the index of target in this array. If the target does not exist, return -$1$.

An original sorted array before rotation is given below:

After rotating this array 6 times, it changes to:

Constraints:

• All values in nums are unique.
• The values in nums are sorted in ascending order.
• The array may have been rotated by some arbitrary number.
• $1 \leq$ nums.length $\leq 1000$
• $-10^4 \leq$ nums[i] $\leq 10^4$
• $-10^4 \leq$ target $\leq 10^4$

Solution#

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach#

A naive approach is to traverse the whole array while searching for our target.

We get the required solution, but at what cost? The time complexity is $O(n)$ because we traverse the array only once, and the space complexity is $O(1)$. Let’s see if we can use the modified binary search pattern to design a more efficient solution.

Optimized approach using modified binary search#

We’ve been provided with a rotated array to apply binary search, which is faster than the above linear approach. We can change the part we have to search based on our three pointers—low, mid, and high.

The slides below illustrate how we would like the algorithm to run:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction#

Let’s start with learning how to use binary search to find a target value in an unrotated sorted array. We can do this either iteratively or recursively. Let’s look at the iterative version first.

Next, let’s look at the recursive version.

Binary search works with arrays that are completely sorted. However, the nums array that we’re provided may not have this property if it’s rotated. Therefore, we have to modify our binary search to accommodate this rotation.

You may notice that at least one half of the array is always sorted—if the array is rotated by less than half the length of the array, at least the second half of the array will still be sorted. Contrarily, if the array is rotated by more than half the length of the array, then at least the first half of the array will be sorted. We can use this property to our advantage and modify the binary_search function as follows:

• If the target value lies within the sorted half of the array, our problem is a basic binary search.

• Otherwise, discard the sorted half and keep examining the unsorted half.

Here is how we go about implementing the iterative approach for this:

The recursive approach is shown below:

Just the code#

Here’s the complete solution to this problem:

The iterative approach:

The recursive approach: