Solutions

# Find the pivot, then binary search in the appropriate half. Or just do a modified binary search that accounts for the rotation.
# binary-search


# Brute force - O(n) time, O(1) space
def search(self, nums: List[int], target: int) -> int:
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

# Find the pivot, then binary search in the appropriate half.
# O(log n) time, O(1) space
def search(nums: list[int], target: int) -> int:
    l, r = 0, len(nums) - 1

    while l < r:
        m = (l + r) // 2
        if nums[m] > nums[r]:
            l = m + 1
        else:
            r = m

    pivot = l

    def binary_search(left: int, right: int) -> int:
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1

    result = binary_search(0, pivot - 1)
    if result != -1:
        return result

    return binary_search(pivot, len(nums) - 1)

# Modified binary search for rotated sorted array
# O(log n) time, O(1) space
def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) -1

    while left <= right: # NB: <=
        mid = left + (right -left) //2

        if nums[mid] == target:
            return mid

        if nums[mid] < nums[right]:
            # right side is ordered, so check if target is in the right half
            if target < nums[mid] or target > nums[right]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # left side is ordered, so check if target is in the left half
            if target > nums[mid] or target < nums[left]:
                left = mid + 1
            else:
                right = mid - 1
    return -1