33. Search in Rotated Sorted Array

link

Key ideas

• If we split the rotated array from the mid, there must be a sorted half and an unsorted half

  • [5, 6, 1, 2, 3, 4] -> [5, 6, 1] (unsorted) + [2, 3, 4] (sorted)

    • [5, 6, 1] -> [5] (sorted) + [6, 1] (unsorted)

  • We can apply regular binary search on the sorted half

  • If we keep splitting the unsorted half, we will eventually either get the answer as nums[mid] or be able to apply regular binary search.

def main(nums, target):
    def bs(l, r, t): 
        if l > r:
            return -1
        m = (l + r) // 2
        if nums[m] == t:
            return m

        if nums[l] >= nums[r]:
            result = bs(l, m - 1, t)
            if result != -1:
                return result
            return bs(m + 1, r, t)


        if nums[m] > t:
            return bs(l, m - 1, t)
        elif nums[m] < t:
            return bs(m + 1, r, t)
    return bs(0, len(nums) - 1, target)

Time complexity: In the worst case, the algorithm will keep splitting the unsorted array and realize the answer is actually in the other half, making it more complex than regular binary search. However, splitting is O(log n), and it would not always happen, so the amortized time complexity should still be O(log n).

Space complexity: The algorithm itself doesn't use any extra space, but we write binary search in a recursive way, and the recursion makes the space complexity O(log n)

With a minor change, this code will work for 81. Search in Rotated Sorted Array II