Search in Rotated Sorted Array

Given a rotated sorted array and a target value, return the index of the target if found in O(log n) time, or -1 if not present.

Language Selection

Choose your preferred programming language

Showing: Python

Search in Rotated Sorted Array

Problem Statement

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.

Examples

Example 1:

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

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Explanation: 3 is not in the array, so return -1.

Example 3:

Input: nums = [1], target = 0
Output: -1
Explanation: 0 is not in the array.

Example 4:

Input: nums = [1], target = 1
Output: 0
Explanation: 1 is found at index 0.

Constraints

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

Algorithm Explanation

Split the problem into two stages:

  1. Find the pivot (the index of the minimum element) using a modified binary search.
  2. Determine which half the target lies in based on the pivot, then run standard binary search on that half.

Finding the pivot:

  • Compare nums[mid] with nums[right].
  • If nums[mid] > nums[right], the pivot is in the right half: left = mid + 1.
  • Otherwise the pivot is at mid or in the left half: right = mid.

Once the pivot is known, we know the array is sorted within [0, pivot-1] and [pivot, n-1]. Check which range contains the target and binary search that range.

Implementation

Python:

def search(nums, target):
    """
    Find pivot, then binary search the correct half.
    Time: O(log n)
    Space: O(1)
    """
    n = len(nums)

    # Step 1: Find the pivot (index of the minimum element)
    left, right = 0, n - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    pivot = left

    # Step 2: Determine which half to search
    if target >= nums[pivot] and target <= nums[n - 1]:
        left, right = pivot, n - 1
    else:
        left, right = 0, pivot - 1

    # Step 3: Standard binary search
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Java:

class Solution {
    /**
     * Find pivot, then binary search the correct half.
     * Time: O(log n)
     * Space: O(1)
     */
    public int search(int[] nums, int target) {
        int n = nums.length;

        // Step 1: Find the pivot (index of the minimum element)
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        int pivot = left;

        // Step 2: Determine which half to search
        if (target >= nums[pivot] && target <= nums[n - 1]) {
            left = pivot;
            right = n - 1;
        } else {
            left = 0;
            right = pivot - 1;
        }

        // Step 3: Standard binary search
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

Go:

// search finds a target in a rotated sorted array by locating the pivot first.
// Time: O(log n), Space: O(1)
func search(nums []int, target int) int {
    n := len(nums)

    // Step 1: Find the pivot (index of the minimum element)
    left, right := 0, n-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            right = mid
        }
    }
    pivot := left

    // Step 2: Determine which half to search
    if target >= nums[pivot] && target <= nums[n-1] {
        left, right = pivot, n-1
    } else {
        left, right = 0, pivot-1
    }

    // Step 3: Standard binary search
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1
}

JavaScript:

/**
 * Find pivot, then binary search the correct half.
 * Time: O(log n)
 * Space: O(1)
 */
function search(nums, target) {
    const n = nums.length;

    // Step 1: Find the pivot (index of the minimum element)
    let left = 0, right = n - 1;
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    const pivot = left;

    // Step 2: Determine which half to search
    if (target >= nums[pivot] && target <= nums[n - 1]) {
        left = pivot;
        right = n - 1;
    } else {
        left = 0;
        right = pivot - 1;
    }

    // Step 3: Standard binary search
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

C#:

public class Solution {
    /// <summary>
    /// Find pivot, then binary search the correct half.
    /// Time: O(log n)
    /// Space: O(1)
    /// </summary>
    public int Search(int[] nums, int target) {
        int n = nums.Length;

        // Step 1: Find the pivot (index of the minimum element)
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        int pivot = left;

        // Step 2: Determine which half to search
        if (target >= nums[pivot] && target <= nums[n - 1]) {
            left = pivot;
            right = n - 1;
        } else {
            left = 0;
            right = pivot - 1;
        }

        // Step 3: Standard binary search
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

Complexity Analysis

  • Time Complexity: O(log n) – two sequential binary searches, each O(log n).
  • Space Complexity: O(1) – only constant extra space is used.

Approach 2: Single-Pass Modified Binary Search (Optimal)

Algorithm Explanation

Instead of two separate binary searches, we can solve the problem in a single pass. The key observation is that at least one half of the array around mid is always sorted. We identify which half is sorted and then decide whether the target falls within that sorted range:

  1. If nums[left] <= nums[mid], the left half [left, mid] is sorted.
    • If nums[left] <= target < nums[mid], search left: right = mid - 1.
    • Otherwise, search right: left = mid + 1.
  2. Else, the right half [mid, right] is sorted.
    • If nums[mid] < target <= nums[right], search right: left = mid + 1.
    • Otherwise, search left: right = mid - 1.

Implementation

Python:

def search_single_pass(nums, target):
    """
    Single-pass modified binary search for rotated sorted array.
    Time: O(log n)
    Space: O(1)
    """
    left, right = 0, len(nums) - 1

    while 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 < 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

Java:

class Solution {
    /**
     * Single-pass modified binary search for rotated sorted array.
     * Time: O(log n)
     * Space: O(1)
     */
    public int searchSinglePass(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int 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;
                }
            }
            // Right half is sorted
            else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}

Go:

// searchSinglePass performs a single-pass modified binary search
// on a rotated sorted array.
// Time: O(log n), Space: O(1)
func searchSinglePass(nums []int, target int) int {
    left, right := 0, 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
}

JavaScript:

/**
 * Single-pass modified binary search for rotated sorted array.
 * Time: O(log n)
 * Space: O(1)
 */
function searchSinglePass(nums, target) {
    let left = 0, right = nums.length - 1;

    while (left <= right) {
        const mid = left + Math.floor((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;
            }
        }
        // Right half is sorted
        else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    return -1;
}

C#:

public class Solution {
    /// <summary>
    /// Single-pass modified binary search for rotated sorted array.
    /// Time: O(log n)
    /// Space: O(1)
    /// </summary>
    public int SearchSinglePass(int[] nums, int target) {
        int left = 0, right = nums.Length - 1;

        while (left <= right) {
            int 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;
                }
            }
            // Right half is sorted
            else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}

Complexity Analysis

  • Time Complexity: O(log n) – one binary search pass.
  • Space Complexity: O(1) – only constant extra space is used.

Key Insights

  1. At Least One Half Is Sorted: In a rotated sorted array, splitting at any midpoint guarantees that at least one of the two halves is fully sorted. This is the crux of the algorithm.
  2. Identifying the Sorted Half: Compare nums[left] with nums[mid]. If nums[left] <= nums[mid], the left half is sorted; otherwise the right half is sorted.
  3. Target Range Check: Once the sorted half is identified, check whether the target falls within that sorted range. If it does, search there; otherwise search the other half.
  4. No Duplicates Simplification: The problem guarantees distinct values, which means nums[left] <= nums[mid] is an unambiguous check. With duplicates (LeetCode #81) the worst case degrades to O(n).
  5. Two-Phase vs Single-Phase: Finding the pivot first is conceptually simpler, but the single-pass approach achieves the same complexity with less code.

Edge Cases

  1. No Rotation: nums = [1,2,3,4,5] – the array is already sorted. Both approaches handle this correctly.
  2. Single Element: nums = [1], target = 1 or target = 0.
  3. Two Elements: nums = [3,1], target = 3 – rotation of a two-element array.
  4. Target at Pivot: nums = [4,5,6,7,0,1,2], target = 0 – target is the minimum element.
  5. Target Is Maximum: nums = [4,5,6,7,0,1,2], target = 7 – target is just before the pivot.
  6. Full Rotation: nums = [1,2,3,4,5] – rotated by n positions is effectively not rotated.

Test Cases

def test_search():
    # Test case 1: Target in the right portion
    assert search([4, 5, 6, 7, 0, 1, 2], 0) == 4

    # Test case 2: Target not found
    assert search([4, 5, 6, 7, 0, 1, 2], 3) == -1

    # Test case 3: Single element not found
    assert search([1], 0) == -1

    # Test case 4: Single element found
    assert search([1], 1) == 0

    # Test case 5: No rotation
    assert search([1, 2, 3, 4, 5], 3) == 2

    # Test case 6: Target at pivot boundary
    assert search([4, 5, 6, 7, 0, 1, 2], 7) == 3

    # Test case 7: Two elements, rotated
    assert search([3, 1], 3) == 0
    assert search([3, 1], 1) == 1

    # Test case 8: Target is the first element
    assert search([4, 5, 6, 7, 0, 1, 2], 4) == 0

    # Test single-pass approach
    assert search_single_pass([4, 5, 6, 7, 0, 1, 2], 0) == 4
    assert search_single_pass([4, 5, 6, 7, 0, 1, 2], 3) == -1
    assert search_single_pass([1], 0) == -1

    print("All tests passed!")

test_search()

Common Mistakes

  1. Wrong Sorted-Half Check: Using nums[left] < nums[mid] (strict) instead of nums[left] <= nums[mid]. When left == mid (two-element subarray), the left half is trivially sorted and the <= is needed.
  2. Boundary Condition Errors: Forgetting to include the boundary element in range checks. For example, nums[left] <= target < nums[mid] must use <= on the left because the target could equal nums[left].
  3. Infinite Loops: Not advancing the pointers correctly. Always move left past mid or right before mid to shrink the search space.
  4. Confusing Pivot Direction: When finding the pivot, comparing nums[mid] with nums[left] vs nums[right] yields different loop structures. Be consistent.
  5. Applying to Duplicates: This approach assumes distinct elements. With duplicates, an extra step is needed to handle nums[left] == nums[mid] == nums[right].

Interview Tips

  1. State the Key Observation: Lead with “at least one half is always sorted” – this is the insight interviewers want to hear.
  2. Draw an Example: Sketch a rotated array on the whiteboard and walk through the pointer movements.
  3. Start with Single-Pass: The single-pass approach is more elegant and shows deeper understanding.
  4. Discuss the Duplicates Variant: Mention LeetCode #81 as a follow-up and explain why duplicates degrade worst-case to O(n).
  5. Compare with Find Minimum: Note that LeetCode #153 (Find Minimum in Rotated Sorted Array) is a related problem that uses the same pivot-finding technique.