Search in Rotated Sorted Array

LeetCode

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.

Initial attempt

Time spent: 39m | Runtime: 59.70% | Memory: 5.18%

• Though the problem seems pretty straightforward, it really threw me for a loop. I got caught up with what my conditionals ought to be and how to ultimately escape with the answer.
• The main lesson was that I should do my problems more methodically (and also practice binary searches).
• The initial attempt was a failure which required looking at the solution.

Solution

• Find the pivot point.
• Find the target.

All the while, the code should stay as clean as possible so things don't get confusing.

Cleaned up code

Time spent: 6m | Runtime: 36.62% | Memory: 23.65%

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        start = 0
        k = n - 1

        while k > start:
            mid = (k + start) // 2

            # This is the main condition we're looking for.  It
            # only happens at one index.
            if nums[mid] < nums[mid - 1]:
                k = start = mid
            elif nums[k] > nums[mid]:
                k = mid
            else:
                start = mid + 1

        pivot = lambda i: (i + k) % n
        start = 0
        end = n - 1
        while end > start:
            mid = (start + end) // 2
            if nums[pivot(mid)] >= target:
                end = mid
            else:
                start = mid + 1

        return pivot(end) if nums[pivot(end)] == target else -1