Search in Rotated Sorted Array

Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed).

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example

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

Approach 1 (Failed):

I dealt with a rotated sorted array yesterday, so I thought that this question would be easy. I was wrong.

I knew I had to implement binary search in some way so that the algorithm will run at O(log n) time. First intuition was to find the minimum in the nums array, sort the array nums by iterating from the minimum index to the end, then perform binary search. Finding the minimum is a O(log n) operation, re-indexing is O(1), and binary search will be also O(log n) which will ultimately result to O(log n) operation.

I do not know if this is a good thing or a bad thing, but my computer’s python interpreter was too slow to finish this operation by the time limit. I had to find another way.

Approach 2:

Then, I thought about both sides of the array when split by a mid index. Even if the minima is not the mid index, there will be at least one side that is completely sorted, Why don’t I try something similar to a binary search from that intution?

1. First initialize pointers in a binary search lo, hi.
2. While lo <= hi, return nums[mid] if it equals to target
3. If not, inspect whether the left side or the right side is sorted
4. If the left side is sorted and if the target is between nums[lo] and nums[mid], update hi = mid - 1
5. If the target is not between the sorted side, update lo = mid + 1
6. On the previous step, we acknowledge that the updated range will not be sorted. We are not performing binary search. We are just removing the part of the array that we know target does not exist.
7. If the right side is sorted and if the target is between nums[mid] and nums[hi], update lo = mid + 1
8. If the target is not between the sorted side, update hi = mid -1
9. Return -1 if there is no value that equals to target

Implementation:

class Solution:


    def search(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums)
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] == target:
                return mid
            elif nums[lo] <= nums[mid]:
                if target >= nums[lo] and target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                if target > nums[mid] and target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return -1
        
        

Complexity Analysis:

Time Complexity:O(log n) where n is the length of the list

Space Complexity: O(1)

Reflection

I knew I had to implement binary search in some way. However, the idea that I could implement something similar to binary search that reduces the search space since we are sure that element is not in a sorted part was hard to understand at first.

Through this question, I realized that I should be more open-minded and really understand why an algorithm works so that I could manipulate it when I need to.

What binary search is really about is reducing the search space by 1/2 when comparing pointers and the mid value. I should not have been fixated by the fact that ‘binary search works only on sorted iterables!’, but rather understand why it works :)