Problem Description

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). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

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 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

My Idea

It is clear from the requirement of a O(log n) time complexity that we need to implement binary search. The modification to the normal binary search here is that after choosing our mid, we check to see which half of the array is sorted and if our target is part of it, or we need to continue searching in the other half. This is required due to the array being rotated. The additional check do not, however, affect the time complexity significantly, which leave us with a O(log n) complexity, just as desired in the problem definition.

My solution

# Time Complexity: O(log n)
def search( nums: list[int], target: int) -> int:
    l = 0
    r = len(nums)-1
    while(l<=r):
        mid = (l+r) // 2
        if nums[mid] == target:
            return mid

        if nums[mid]>=nums[r]:
            if nums[l]<=target and target<nums[mid]:
                r=mid-1
            else:
                l=mid+1
        else:
            if nums[mid]<target and target <=nums[r]:
                l=mid+1
            else:
                r=mid-1
    return -1