Search in a rotated sorted array

Problem

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. For example, \([0,1,2,4,5,6,7]\) might become \([4,5,6,7,0,1,2]\). You are given a target value to search. If found in the array return its index, otherwise return \(-1\).

Note: You may assume no duplicate exists in the array.

Note: Your algorithm's runtime complexity must be in the order of \(O(log n)\).

Example 1:

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

Example 2:

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

Input

• nums - an array of integers
• target - integer value to search for

Approach

This is a classic textbook problem with a slight twist. The brute force approach is to linearly traverse the array and return the index of a value that matches target as soon as you encounter one. This is \(O(n)\), which is good, but we could do better.

Since the array is partially sorted, it turns out that this array is still a good candidate for binary search. The key to solving this is to understand your boundaries thoroughly.

The traditional binary search algorithm gives you access to the lowest index, the highest index, and using the two indices you can determine the middle index. The cycle (where the smallest number is right after the largest number) can only exist in one half of the array: either the left-half, or the right-half. Therefore...

• If \(A[lowest] < A[middle]\), then the left half is sorted normally, and the right half contains the cycle.
• Likewise, if \(A[middle] < A[highest]\), then the right half is sorted normally, and the left half contains the cycle.

Once you know where the cycle is, all you have to do is compare your target value against what you know and don't know, i.e. if the target value is not in the sorted half of the array, then it must be in the array where the cycle is.

Solution

    def search(self, nums: 'List[int]', target: 'int') -> 'int':

        def _find(lo, hi, target):
            if lo > hi:
                return -1

            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            elif nums[lo] < nums[mid] and (target < nums[lo] or target > nums[mid]):  # the left half is sorted.. so cycle must be in right half
                return _find(mid+1, hi, target)
            elif nums[lo] < nums[mid] and nums[lo] <= target < nums[mid]:
                return _find(lo, mid-1, target)
            elif nums[mid] < nums[hi] and (target < nums[mid] or target > nums[hi]):
                return _find(lo, mid-1, target)
            else:
                return _find(mid+1, hi, target)

        return _find(0, len(nums)-1, target)