LeetCode #33: Search in Rotated Sorted Array

LeetCode Solutions

https://leetcode.com/problems/search-in-rotated-sorted-array/

To solve this problem in Python 3, we can use a modified binary search algorithm to search for the target element in the sorted rotated array.

Here are the steps to follow:

  1. Initialize two pointers, left and right, to the first and last indices of the input array nums, respectively.
  2. Perform binary search until the left pointer is equal to or greater than the right pointer.
  3. Calculate the mid index as the average of left and right.
  4. If nums[mid] == target, return mid.
  5. If nums[left] <= nums[mid], the left half is sorted.
    • If nums[left] <= target < nums[mid], the target is in the left half. Set right to mid - 1.
    • Otherwise, the target is in the right half. Set left to mid + 1.
  6. If nums[mid] < nums[right], the right half is sorted.
    • If nums[mid] < target <= nums[right], the target is in the right half. Set left to mid + 1.
    • Otherwise, the target is in the left half. Set right to mid - 1.

Here’s the Python 3 code that implements this approach:

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

In this code, we first initialize two pointers, left and right, to the first and last indices of the input array nums, respectively. We then perform binary search by calculating the mid index and comparing nums[mid] to target.

If nums[mid] == target, we return mid. Otherwise, we check if the left half or right half is sorted by comparing nums[left] to nums[mid]. Depending on whether the left half or right half is sorted, we check if the target is in that half of the array. We then update left or right accordingly and repeat the binary search until the target is found or the pointers left and right cross each other.

Finally, we return -1 if the target is not found in the input array.

Time and Space Complexity

The time complexity of the solution is O(log n) because it uses binary search to find the target element. In the worst case, the algorithm needs to search through half of the input array on each iteration, resulting in O(log n) time complexity.

The space complexity of the solution is O(1) because it only uses a constant amount of extra space to store the pointers left, right, and mid. Thus, the space used does not depend on the size of the input array.