Search in Rotated Sorted Array

Problem Statement:

Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4

Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1

Solution One:

We are all familiar with binary search. Imagine that our array is sorted in ascending order, we do not have any rotation, how can we do binary search? Let’s lo and hi be the smallest index and largest the index of an array, we calculate the mid = (lo + hi) / 2, and compare the num[mid] value with our target value. If target value is greater than or equal to num[mid], we throw away left half of the array, else we throw away the right half of the array. We keep calculating the new mid value based on the remaining array.

So the general idea for solution one is to first calculate the corresponding index for the rotated array. Let’s say we have an original array nums = [0, 1, 2, 4, 5, 6, 7] (see fig 1), we have the corresponding index [0 – 6].

Now we rotate the array, and the array becomes [4, 5, 6, 7, 0, 1, 2]. We can see the new index should also be [0 – 6]. If we map the original index to the new table, we can see the original index should be [3, 4, 5, 6, 0, 1, 2]. If we observe the modification, we can see that after the rotation, the index is shifted by a bias value mod the total length. In this case, the bias is 4. If we look at the value 0, we can the original index is 0, and new index is 4, while the value 1 is mapped from 1->5, value 2 is 2->6. How about the value 4? It is mapped by its original index 3 plus bias 4, and mod by total length 7, so we get the new index 0.

Since we can see a clear corresponding mapping between new array and old array, so our mission is two:

1. Find a way to calculate the bias;

2. Do a binary search on the original array. We can calculate the original middle value based on bias value.

Note the algorithm should have time complexity O(lg n), so both the two steps should have these limitations.

Calculate the bias:

We can define we want to calculate the new index of the smallest element (whose original index should be 0, of course we can try to find the largest element, the idea should be similar). Since we need to guarantee the time complexity is O(lg n), when we  try to find the new index (in order to calculate the bias), we need to do binary search as well. We have two options:

1. We compare middle with start value:

if mid > start:

We can see that the smaller value should be in the left of the mid, we need to get rid of the right of half of the array. However, if mid < start:

Since the original array is sorted in ascending order, and the new array is rotated by only one pivot, we cannot find the smaller values in the right half of the array, we need to get rid right half of the array. This could be a problem, since we have to get rid of the right half of the array no matter mid is greater or smaller than start value, we cannot update start pointer any more.

2. We compare the middle value with the end value:

If mid < end:

We can see we need to find the smaller value in the left half of the array.

If mid > end:

We can see the smaller value is in the right half of the array, we can get rid of the left half of the array. So we need to compare the middle value and end value. When mid > end, we update start = mid + 1, else, we update end = mid, until start equals to end. (Note we need to update start = mid + 1 in order to avoid infinite loop, look at the picture below)

When we find the index of the smallest value (last start value) in the new array, we can know the bias should the start value since the original index of the smallest element should 0.

When we get the bias, we can use this bias to calculate the original index of all the elements, and do a normal binary search to find the target value.

Time Complexity: O(lg n)

Space Complexity: O(1)

Solution Two:

We can see that a rotated array can be divided into two different sub arrays by the pivot point, and each sub array should be sorted in descending order. For example:

[ 4 5 6 7 1 2 3 ] =>[ 4 5 6 7 ] and [ 1 2 3 ] .

[1 2 3 4] => [1 2 3 4] and [].

So we can look at this problem from another perspective: we can try to find whether our target value is in one of the sub arrays, if the value is in the sub array, we do not do any modification about the values, if not, we change the value in this sub array to be infinite number or negative infinite number accordingly based on whether target is greater than nums[0]. For example:

[ 4 5 6 7 1 2 3 ], target  = 5, [ 4 5 6 7 inf inf inf ];

[ 4 5 6 7 1 2 3 ], target  = 2, [ -inf -inf – inf -inf 1 2 3];

Then the problem is converted to normal binary search solution. We only need to care about the nums[mid], we can compare the target value with nums[mid], infinite or -infinite. We can define the value be the infinite or -infinite based on the following rules:

If nums[mid] and target both less than nums[0] (Here, the both greater than nums[0] is not working), we can keep nums[mid] as its original value, else, we need to change the mid = target > nums[0] ? inf : -inf. Then we can do the normal binary search.

Two examples:

[ 4 5 6 7 1 2 3]，If target = 5，so the array will be [ 4 5 6 7 inf inf inf ]。nums [ mid ] = 7，target > nums [ 0 ]，nums [ mid ] > nums [ 0 ]，so we can keep mid = 7;

[ 4 5 6 7 1 2 3]，if target = 2，the array can be [ – inf – inf – inf – inf 1 2 3]。nums [ mid ] = 7，target < nums [ 0 ]，nums [ mid ] > nums [ 0 ]，so the mid = – inf.

Time Complexity: O(lg n)

Space Complexity: O(1)

Solution Three:

Ideally, we can always split the rotated sorted arrays from any position into two sub arrays and at least one sub array is sorted. So we can always split the arrays, and check if the target is in the sorted arrays, if it is true, we throw away the unsorted array, else, we throw away the sorted array. Then we keep dividing the remaining arrays.

How can we check if an array is sorted? we only need to check whether nums[start] <= nums[mid]. The reason is simple, because the original array is sorted in ascending order, so when we rotate the array and split, if the first element is less than middle, which means they should form an ascending sequence.

Time Complexity: O(lg n)

Space Complexity: O(1)

That’s all for today… Thanks for reading…