Leetcode 81. Search in Rotated Sorted Array II

Problem

Leetcode 81 - Search in Rotated Sorted Array II

Example:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Approach

Similar to the quesiton previously, our logic follows the same.

In rotated array, there are 2 parts, left and right.

• If target == nums[mid], we simply return True
• If left to mid is sorted
  • If target is a value between left to mid, move right pointer
  • else target must be in right side of the array, move left pointer
• Else if left to mid isn’t sorted
  • If target is a value between mid to right, move left poitner
  • else target must be in left side of the array, move right pointer
• Else meaning that our value from left to right is repeated value, thus increment the left pointer by 1

Here is the Python code for the solution:

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        left, right = 0, len(nums)-1

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

            if nums[mid] == target:
                return True

            # if left to mid is sorted
            if nums[left] < nums[mid]:
                # if target is in the left portion of the array
                if nums[left] <= target < nums[mid]:
                    right = mid-1
                # target must be on the right portion of the array
                else:
                    left = mid+1
            
            # if left to mid isn't sorted
            elif nums[left] > nums[mid]:
                # if target is in the right portion of the array
                if nums[mid] < target <= nums[right]:
                    left = mid+1
                # target must be on the left portion of the array
                else:
                    right = mid-1

            else:
                left += 1

        return False

Time Complexity and Space Complexity

Time Complexity: $O(log n)$

Space Complexity: $O(1)$