LeetCode 33: Search in Rotated Sorted Array Solution in Python Explained

Problem Statement

LeetCode 33, Search in Rotated Sorted Array, is a medium-level problem where you’re given a sorted array nums that has been rotated an unknown number of times and a target integer target. Your task is to return the index of target in nums, or -1 if it’s not present. The array contains unique elements, and you must achieve this in O(log n) time complexity.

Constraints

1 <= nums.length <= 5000: Array length is between 1 and 5000.
-10^4 <= nums[i], target <= 10^4: Elements and target are within this range.
All values in nums are unique.
nums is sorted in ascending order and rotated at some pivot.

Example

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Explanation: 0 is at index 4 in the rotated array.

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Explanation: 3 isn’t in the array.

Input: nums = [1], target = 0
Output: -1
Explanation: Single-element array, 0 not found.

Understanding the Problem

How do you solve LeetCode 33: Search in Rotated Sorted Array in Python? For nums = [4,5,6,7,0,1,2] and target = 0, you need to find 0 at index 4. The array is sorted but rotated (e.g., originally [0,1,2,4,5,6,7] shifted right), so standard binary search won’t work directly. We’ll explore two approaches: a Modified Binary Search Solution (optimal and primary) and an Alternative with Linear Search (simple but slower). The modified binary search leverages the rotated structure to achieve O(log n) time.

Solution 1: Modified Binary Search Approach (Primary)

Explanation

Since the array is rotated but still partially sorted, use binary search with a twist: determine which half is sorted and whether the target lies in it. Compare the middle element with the leftmost to identify the sorted portion, then adjust the search range accordingly.

Here’s a visual for [4,5,6,7,0,1,2], target = 0:

Initial: left = 0, right = 6, mid = 3 (7)
Left sorted: [4,5,6,7] > 0, search right: [0,1,2]
Next: left = 4, right = 6, mid = 5 (1)
Right sorted: [1,2] < 0, search left: [0]
Found: mid = 4 (0)

Initialize Pointers.

left = 0, right = len(nums) - 1.

Binary Search with Rotation Check.

Check if left or right half is sorted, adjust based on target.

Return Index.

Return mid if target found, -1 if not.

Step-by-Step Example

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

We need index 4.

Goal: Find target 0.
Result for Reference: 4.
Start: nums = [4,5,6,7,0,1,2], left = 0, right = 6.
Step 1: mid = 3, nums[3] = 7.

nums[0] = 4 ≤ 7, left half [4,5,6,7] sorted.
0 < 4 or 0 > 7, not in [4,5,6,7], search right.
left = 4, right = 6.

Step 2: mid = 5, nums[5] = 1.

nums[4] = 0 ≤ 1, left half [0,1] sorted.
0 ≥ 0 and 0 ≤ 1, in [0,1], search left.
right = 5.

Step 3: mid = 4, nums[4] = 0.

0 == 0, found.

Finish: Return 4.

Example 2: nums = [4,5,6,7,0,1,2], target = 3

We need -1.

Goal: Find target 3.
Result for Reference: -1.
Start: left = 0, right = 6.
Step 1: mid = 3, nums[3] = 7.

nums[0] = 4 ≤ 7, left sorted, 3 < 4, search right.
left = 4, right = 6.

Step 2: mid = 5, nums[5] = 1.

nums[4] = 0 ≤ 1, left sorted, 3 > 1, search right.
left = 6, right = 6.

Step 3: mid = 6, nums[6] = 2.

3 > 2, left = 7 > right = 6, stop.

Finish: Return -1.

How the Code Works (Modified Binary Search)

Here’s the Python code with line-by-line explanation:

def search(nums: list[int], target: int) -> int:
    # Line 1: Initialize pointers
    left, right = 0, len(nums) - 1

    # Line 2: Binary search loop
    while left <= right:
        # Line 3: Compute mid
        mid = (left + right) // 2

        # Line 4: If target found
        if nums[mid] == target:
            return mid

        # Line 5: Check if left half is sorted
        if nums[left] <= nums[mid]:
            # Line 6: Target in left half?
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Line 7: Right half must be sorted
        else:
            # Line 8: Target in right half?
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    # Line 9: Target not found
    return -1

Alternative: Linear Search Approach

Explanation

Scan the array linearly to find the target. This is simple but doesn’t meet the O(log n) requirement, included for clarity.

Iterate Array.
Check Each Element.
Return Index or -1.

Step-by-Step Example (Alternative)

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

Goal: Index 4.
Step 1: i = 0, 4 ≠ 0.
Step 2: i = 4, 0 = 0, found.
Finish: Return 4.

How the Code Works (Linear)

def searchLinear(nums: list[int], target: int) -> int:
    # Line 1: Scan array
    for i in range(len(nums)):
        # Line 2: Check each element
        if nums[i] == target:
            return i
    # Line 3: Not found
    return -1

Complexity

Modified Binary Search:

Time: O(log n) – Binary search on rotated array.
Space: O(1) – No extra space.

Linear Search:

Time: O(n) – Single pass.
Space: O(1).

Efficiency Notes

Modified Binary Search is O(log n), meeting LeetCode’s requirement, while Linear Search (O(n)) is too slow but easier to grasp.

Key Insights

Tips to master LeetCode 33:

Sorted Halves: One half is always sorted—use it!
Pivot Logic: Compare mid with ends to find the sorted part.
Logarithmic Goal: Think binary, not linear.

Additional Example

For nums = [3,1], target = 1:

Goal: Index 1.
Binary: mid = 0, 3 > 1, left sorted, search right, mid = 1, found.
Result: 1.

Edge Cases

Single Element: [1], target = 1 – Return 0.
Not Rotated: [1,2,3], target = 2 – Return 1.
Target Missing: [4,5,6], target = 1 – Return -1.

Final Thoughts

The Modified Binary Search solution is a masterpiece for LeetCode 33 in Python—fast, clever, and logarithmic. For a related challenge, try LeetCode 32: Longest Valid Parentheses to test your string skills! Ready to nail it? Solve LeetCode 33 on LeetCode now and experiment with rotated arrays like [5,1,3] or [4,5,6,7] to boost your binary search game. Dive in and ace it!