33. Search in Rotated Sorted Array — LeetCode(Python)

I got you!

Problem:

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

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 in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

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

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• -104 <= target <= 104

Solution:

l, r = 0, len(nums) - 1
        
while l <= r:
    mid = (l + r) // 2
    if nums[mid] == target:
        return mid
            
    if nums[mid] >= nums[l]: #we are in the left sorted portion
        if target > nums[mid] or target < nums[l]: #target is not in left subarray
            l = mid + 1 #so go to right subarray
        else:
            r = mid - 1
                    
    elif nums[mid] <= nums[r]: #right sorted portion
        if target < nums[mid] or target > nums[r]: #target is not in right subarray
            r = mid - 1 #so check in left
        else:
            l = mid + 1
                    
return -1

Explanation —

We use binary search here. We are given a sorted array that has been rotated a given number of times.

We perform a basic binary search on the array.

Consider the following array for better understanding while going through the points below:

[4,5,6,7,0,1,2]

• First, we come to the mid element of the array nums. We return mid if nums[mid] == target.
• If this element is greater than the number at the left pointer, we are in the left sorted array.
• If the target value is not in this left subarray, we check the right subarray by shifting our left pointer.
• If the target value is in this subarray, we shift our right pointer to the end of this subarray.
• Else if this element is smaller than the number at the right pointer, we are in the right sorted array.
• In this case, if the target value is not in the right sorted array, we shift our right pointer to only check the left portion of the array.
• If, however, the target value is in this subarray, we shift our left pointer to the beginning of this subarray.

Finally, we return -1 if we terminate the while loop.

Time and Space Complexity —

Since, this is a binary search procedure, our time and space complexities are the same.

Thus, if n is the length of the array nums,

Time Complexity: O(log(n))

Space Complexity: O(1)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏