Python Programming Challenge 27: Search in Rotated Sorted Array

For today’s programming challenge, we’ll be discussing the Search in Rotated Sorted Array question from Leetcode.

The Search in Rotated Sorted Array Problem

As the name suggests, this problem requires us to search for an element in a rotated sorted array.

A rotated sorted array refers to one where elements are sorted before the array is split into two subarrays (not necessarily of the same length). The two subarrays are then switched so that the subarray with the larger numbers is in front of the other subarray.

For instance, suppose we have a sorted array called nums, where

nums = [2, 4, 5, 7, 8, 9, 12, 15, 20]

We can split nums into two subarrays – [2, 4, 5, 7] and [8, 9, 12, 15, 20] and rotate them. This gives us an updated array, where

nums becomes [8, 9, 12, 15, 20, 2, 4, 5, 7]

Our job is to write a function called search() that takes two arguments – nums and target.

nums is a rotated sorted array and target is the element that we are required to find. If target is found, the function returns the index of target. Else, the function returns -1.

Suggested Approach

To solve the Search in Rotated Sorted Array problem, we’ll be using a modified version of the binary search algorithm.

If you are unfamiliar with binary search, be sure to refer to the previous post where we discussed how binary search works. Our suggested approach for today is based on the while loop solution in that post.

In the previous post, we mentioned that to do a binary search, we repeatedly compare the target with the element in the middle of the list (or sublist).

This works very well for a sorted list. If the target is greater than the middle element, we know that it is in the upper half of the list. If it is smaller, it is in the lower half.

However, if the list is not a sorted list, this technique does not work.

Our current problem presents us with a sort of ‘hybrid’ list, where the list is sorted, but rotated. As such, if we want to do a binary search, we need to make some modifications.

As the focus of a binary search involves comparing the target with the middle element, we’ll update the middle element before we do any comparison.

Here’s how it works.

Determine Whether The Target Is In The Same Sublist As The Middle Element

First, we need to determine whether the target is in the same sublist as the middle element. If it is, we do not need to make any modifications to the middle element.

This is because any element that is in the same sublist as nums[middle] ‘behaves as expected’. If it is larger than nums[middle], it’ll be in the upper half of the entire list. If it is smaller, it’ll be in the lower half.

For instance, if nums = [9, 10, 13, 1, 2, 4, 5, 6, 7, 8], we can view nums as consisting of two sorted sublists – [9, 10, 13] and [1, 2, 4, 5, 6, 7, 8].

As nums consists of 10 elements, with indexes starting from 0 to 9, we can determine the middle element using the calculations below:

middle 
= (0+9)//2
= 4

nums[middle]
= nums[4]
= 2

Any number that is in the same sublist as nums[4] (i.e elements in the sublist [1, 2, 4, 5, 6, 7, 8]) behaves normally.

If the number is greater than nums[4] (which is 2), it is in the upper half of the entire list. If it is smaller than nums[4], it is in the lower half.

In contrast, any number that is not in the same sublist as nums[4] (i.e. elements in the sublist [9, 10, 13]) does not ‘behave normally’.

The diagram below provides a graphical illustration of this concept.

The two sublists are highlighted in different shades of blue (dark blue for the sublist with the larger numbers, and light blue for the sublist with the smaller numbers).

The light blue sublist contains the middle element. Any number inside this sublist behaves normally.

For instance, 6 is in the light blue sublist. As it is greater than nums[middle], it is in the upper half of the entire list.

1, which is also in the light blue sublist, is smaller than nums[middle]. Hence, it is in the lower half of the entire list.

In contrast, if we look at an element in the dark blue sublist, we see that the same relationship does not hold. Although 10 is greater than nums[middle], it is in the lower half of the entire list.

Dealing With Cases Where The Target Is Not In The Same Sublist As nums[middle]

The difficult part for this challenge is dealing with cases where target is not in the same sublist as nums[middle].

For instance, with reference to the diagram above, if target is 10, we cannot compare 10 with nums[middle] and decide to take the upper half. That’ll discard the correct half that target is in.

For cases like this, we need to update the value of nums[middle]. There are two cases to consider.

Case 1

The first case is when target is greater than nums[middle] but is in the lower half.

An example is when nums = [9, 10, 13, 1, 2, 4, 5, 6, 7, 8] and target = 10, as shown in the diagram below:

Case 2

The second case is when target is smaller than nums[middle] but is in the upper half.

For instance, nums = [9, 10, 13, 14, 16, 17, 2, 4, 5, 7] and target = 5:

Both cases will fail if we use a normal binary search to look for the target.

In order to perform a binary search for these 2 cases, we need to update the value of nums[middle] before we do a comparison to decide which half to retain.

For case 1, we want to keep the lower half. Hence, we need to ensure that nums[middle] is greater than target. To achieve this, we can update nums[middle] to a very big number. For convenience, we’ll update nums[middle] to positive infinity.

For case 2, we want to keep the upper half. Hence, we need to ensure that nums[middle] is smaller than target. For convenience, we’ll update nums[middle] to negative infinity.

Once we’ve updated nums[middle] to an appropriate value, we can do a normal binary search and retain the correct half that we want.

How To Determine Case 1 and Case 2?

To determine whether target is in the same sublist as nums[middle], we need to compare target with nums[middle] and nums[0].

Case 1

For case 1, if target is not in the same sublist as nums[middle] (i.e. target is in the dark blue sublist), the following conditions must be met:

1. target > nums[middle]
2. target >= nums[0] (i.e. target is in the same sublist as nums[0])
3. nums[0] > nums[middle]

Case 2

For case 2, if target is not in the same sublist as nums[middle] (i.e. target is in the light blue sublist), the following conditions must be met:

1. target < nums[0]
2. target < nums[middle]
3. nums[0] <= nums[middle] (i.e. nums[middle] is in the same sublist as nums[0])

Based on the description above, try solving the Search in Rotated Sorted Array challenge yourself.

Suggested Solution

Here’s the suggested solution for the Search in Rotated Sorted Array challenge.

def search(nums, target):

    low = 0
    high = len(nums) - 1
    middle = 0

    while low <= high:

        middle = (low + high)//2

        if target >= nums[0] > nums[middle]:
            nums[middle] = float('inf')
        elif target < nums[0] <= nums[middle]:
            nums[middle] = -1*float('inf')

        if target == nums[middle]:
            return middle
        elif target > nums[middle]:
            low = middle + 1
        else:
            high = middle - 1

    return -1

If you study the code above, you’ll see that it is VERY similar to the binarySearch() function in our previous post – How to Do a Binary Search in Python.

The only difference is we added four lines of code from lines 11 to 14. Here, we use an if statement to determine whether target is in the same sublist as nums[middle].

If target >= nums[0] > nums[middle], we have case 1 as discussed in the suggested approach above. Hence, we update nums[middle] to positive infinity (using the built-in float('inf') function).

On the other hand, if target < nums[0] <= nums[middle], we have case 2. Hence, we update nums[middle] to negative infinity.

Other than that, this function is identical to the binarySearch() function in the previous post.