LeetCode 33 - Search in Rotated Sorted Array

LeetCode Problem 33

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

The problem gives us an array that was originally sorted in ascending order, but may have been rotated at some pivot point. A rotation means that some prefix of the sorted array was moved to the end while preserving the relative order of elements.

For example, the sorted array:

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

could be rotated into:

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

The important detail is that the array still contains two individually sorted portions. The rotation introduces a "break" point where large values are followed by small values.

We are also given a target value, and we must return the index where the target appears in the array. If the target does not exist, we return -1.

The challenge is not simply finding the target. The challenge is meeting the required runtime complexity of O(log n). A linear scan would work functionally, but it would take O(n) time. The problem specifically requires a logarithmic solution, which strongly suggests binary search.

The constraints tell us several important things:

• The array length is at least 1, so we never receive an empty array.
• All elements are distinct, which is extremely important because it guarantees we can determine which side of the array is sorted during binary search.
• The array was originally sorted, meaning most of the structure needed for binary search still exists.
• The required runtime is O(log n), meaning we must discard half the search space at every step.

Several edge cases are important:

• The array may not actually be rotated at all.
• The array may contain only one element.
• The target may not exist in the array.
• The rotation point may appear near the beginning or end.
• The target may lie on either side of the rotation pivot.

A naive binary search fails because the array is not globally sorted. However, one side of the current search range is always sorted, and that observation is the key to the optimal solution.

Approaches

Brute Force Approach

The simplest approach is to iterate through the array from left to right and compare every element against the target.

If we find the target, we return its index immediately. If we reach the end without finding it, we return -1.

This approach is correct because it checks every possible position where the target could appear. Since the problem guarantees distinct values, the first match is the only match.

However, this solution requires scanning the entire array in the worst case. If the target is absent, or located near the end, we examine all elements.

Because the runtime is O(n), this does not satisfy the required logarithmic complexity.

Optimal Binary Search Approach

The key observation is that although the array is rotated, at least one half of the current search interval is always sorted.

During binary search:

• We compute the middle index.

• One of these ranges must be sorted:

• left -> mid

• mid -> right

Once we identify the sorted half, we can determine whether the target lies inside that range.

If the target belongs to the sorted half, we continue searching there. Otherwise, we search the opposite half.

This preserves the logarithmic behavior of binary search because each iteration eliminates half of the remaining search space.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Scans every element sequentially
Optimal	O(log n)	O(1)	Modified binary search using sorted-half detection

Algorithm Walkthrough

1. Initialize two pointers, left and right, representing the current search boundaries.

Initially:

• left = 0
• right = len(nums) - 1

These pointers define the portion of the array we are currently searching. 2. Continue searching while left <= right.

This condition ensures there are still candidate elements remaining. 3. Compute the middle index:

mid = (left + right) // 2

The middle element is the current candidate. 4. If nums[mid] == target, return mid.

We found the target, so the search is complete. 5. Determine which half is sorted.

Because the array contains distinct values and originated from a sorted array, at least one side must remain sorted.

We check:

if nums[left] <= nums[mid]:

If true, the left half is sorted.

Otherwise, the right half is sorted. 6. If the left half is sorted, determine whether the target lies inside it.

The target belongs in the left half if:

nums[left] <= target < nums[mid]

If this condition is true, discard the right half:

right = mid - 1

Otherwise, discard the left half:

left = mid + 1

7. If the right half is sorted, determine whether the target lies inside it.

The target belongs in the right half if:

nums[mid] < target <= nums[right]

If true:

left = mid + 1

Otherwise:

right = mid - 1

8. If the loop finishes without returning, the target does not exist.

Return -1.

Why it works

The algorithm works because every iteration guarantees that one side of the array is properly sorted. Since the target can only belong either inside or outside that sorted interval, we can safely discard half of the remaining search space each time.

This preserves the core invariant of binary search: after every iteration, the target, if it exists, must still lie within the updated search boundaries.

Because the search interval shrinks by half each iteration, the runtime remains O(log n).

Python Solution

from typing import List

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

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

            if nums[mid] == target:
                return mid

            # Left half is sorted
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1

            # Right half is sorted
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

The implementation begins by initializing two pointers that represent the current search interval.

Inside the loop, we calculate the middle index and immediately check whether the middle element matches the target. This is identical to ordinary binary search.

The important difference appears in the next section. Since the array is rotated, we cannot directly compare the target against the middle value alone. Instead, we first determine which half is sorted.

The condition:

nums[left] <= nums[mid]

tells us whether the left half is sorted. If true, we then check whether the target falls inside that sorted interval.

If the target belongs there, we move the right pointer inward. Otherwise, we discard the left half and continue searching the right half.

The opposite logic applies when the right half is sorted.

Eventually, either the target is found or the search interval becomes empty.

Go Solution

func search(nums []int, target int) int {
    left := 0
    right := len(nums) - 1

    for left <= right {
        mid := left + (right-left)/2

        if nums[mid] == target {
            return mid
        }

        // Left half is sorted
        if nums[left] <= nums[mid] {
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            // Right half is sorted
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }

    return -1
}

The Go implementation follows exactly the same logic as the Python version.

One small implementation detail is the computation of the middle index:

mid := left + (right-left)/2

This avoids potential integer overflow that could occur with:

(left + right) / 2

Although overflow is not realistically possible under this problem's constraints, this pattern is considered best practice in Go and many other languages.

Go slices are used directly, and no extra memory allocation is required.

Worked Examples

Example 1

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

Iteration Trace

left	right	mid	nums[mid]	Sorted Half	Action
0	6	3	7	Left half sorted [4,5,6,7]	Target not in left half, move left
4	6	5	1	Left half sorted [0,1]	Target in left half, move right
4	4	4	0	Found target	Return 4

Output:

4

Example 2

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

Iteration Trace

left	right	mid	nums[mid]	Sorted Half	Action
0	6	3	7	Left half sorted	Target not there, move left
4	6	5	1	Left half sorted	Target not there, move left
6	6	6	2	Left half sorted	Target not there, move left
7	6	-	-	Search ends	Return -1

Output:

-1

Example 3

Input: nums = [1], target = 0

Iteration Trace

left	right	mid	nums[mid]	Action
0	0	0	1	Target not found, move left
1	0	-	-	Search ends

Output:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Each iteration removes half the remaining search space
Space	O(1)	Only a few variables are used

The runtime remains logarithmic because the algorithm behaves like binary search. Every iteration discards half of the remaining elements based on which side is sorted and whether the target can lie inside that interval.

The space complexity is constant because the algorithm uses only a fixed number of variables regardless of input size.

Test Cases

solution = Solution()

# Provided examples
assert solution.search([4,5,6,7,0,1,2], 0) == 4  # target exists after pivot
assert solution.search([4,5,6,7,0,1,2], 3) == -1  # target absent
assert solution.search([1], 0) == -1  # single-element absent

# Single-element present
assert solution.search([1], 1) == 0  # smallest valid array

# No rotation
assert solution.search([1,2,3,4,5], 3) == 2  # standard binary search case

# Rotation near beginning
assert solution.search([5,1,2,3,4], 1) == 1  # pivot near start

# Rotation near end
assert solution.search([2,3,4,5,1], 1) == 4  # pivot near end

# Target is first element
assert solution.search([6,7,1,2,3,4,5], 6) == 0  # left boundary target

# Target is last element
assert solution.search([6,7,1,2,3,4,5], 5) == 6  # right boundary target

# Target equals pivot value
assert solution.search([4,5,6,1,2,3], 1) == 3  # minimum element

# Target absent in rotated array
assert solution.search([6,7,8,1,2,3,4,5], 9) == -1  # outside range

# Two-element rotated array
assert solution.search([3,1], 1) == 1  # minimal non-trivial rotation

# Two-element non-rotated array
assert solution.search([1,3], 3) == 1  # basic binary search behavior

Test Summary

Test	Why
[4,5,6,7,0,1,2], target=0	Standard rotated-array success case
[4,5,6,7,0,1,2], target=3	Standard rotated-array failure case
[1], target=0	Single-element absent case
[1], target=1	Single-element present case
[1,2,3,4,5], target=3	No rotation present
[5,1,2,3,4], target=1	Pivot near beginning
[2,3,4,5,1], target=1	Pivot near end
[6,7,1,2,3,4,5], target=6	Target at left boundary
[6,7,1,2,3,4,5], target=5	Target at right boundary
[4,5,6,1,2,3], target=1	Target equals pivot element
[6,7,8,1,2,3,4,5], target=9	Missing target outside range
[3,1], target=1	Small rotated array
[1,3], target=3	Small non-rotated array

Edge Cases

Single-Element Arrays

A single-element array is the smallest possible valid input. This case is easy to mishandle if the binary search loop conditions are incorrect.

For example:

nums = [1], target = 0

The implementation handles this correctly because the loop still executes once with left == right == mid. After checking the single element, the pointers move appropriately and the loop terminates cleanly.

Arrays That Are Not Rotated

The array may already be fully sorted with no rotation at all.

For example:

[1,2,3,4,5]

In this situation, the condition:

nums[left] <= nums[mid]

will usually remain true, meaning the algorithm behaves exactly like ordinary binary search. No special-case logic is required.

Target Near the Rotation Pivot

The rotation pivot is the location where ordering changes abruptly. Targets near this boundary are common sources of bugs because naive comparisons can incorrectly discard the wrong half.

For example:

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

The implementation safely handles this because it never assumes the entire array is sorted. Instead, it identifies which half is currently sorted and checks whether the target belongs inside that specific interval.

Target Does Not Exist

If the target is absent, the algorithm must eventually eliminate the entire search range and return -1.

For example:

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

The implementation guarantees termination because each iteration strictly shrinks the search interval. Eventually, left becomes greater than right, signaling that the target cannot exist in the array.