[Coderust] Search in Rotated Sorted Array

 

 

Problem

 

 

---

 

Solution

 

Time complexity constraint is O(log N) -> perform binary search

First determine the how the array rotated, then do the search

 

 """
            No rotated:
            1 2 3 4 5 6 7
                 mid
                 
            left rotated: pivot at the left side of the origin sorted array, A[mid] >= A[left]
            3 4 5 6 7 1 2
                 mid
            search in A[left] ~ A [mid] if A[left] <= target < A[mid] else, search right side
            
            right rotated: pivot at the right side of the origin sorted array, A[mid] < A[left]
            6 7 1 2 3 4 5
                 mid          
            search in A[mid] ~ A[right] if A[mid] < target <= A[right] else, search left side
            """

 

Time Complexity

O(log N)

 

 

Space Complexity

O(1)

 

 

 

 

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