#33

Search in Rotated Sorted Array

medium· Binary Searchruns: 0

There is an integer array nums sorted in ascending order with distinct values that may have been rotated at an unknown pivot. 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. The algorithm must run in O(log n) time.

wpm 0acc 100%time 0:000 / 613

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.