Learning On the Way

33. Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array.

class Solution: 
    def search(self, nums: List[int], target: int) -> int: 
        start, end = 0, len(nums) - 1 
        while start <= end: 
            mid = start + (end - start) // 2 
            if nums[mid] == target: 
                return mid 
            elif nums[mid] >= nums[start]: 
                if target >= nums[start] and target < nums[mid]: 
                    end = mid - 1 
                else: 
                    start = mid + 1 
            else: 
                if target <= nums[end] and target > nums[mid]: 
                    start = mid + 1 
                else: 
                    end = mid - 1 
        return -1