There is an integer array nums sorted in ascending order (with distinct values), rotated at an unknown pivot. Given nums and target, return the index of target 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

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
  • -10^4 <= nums[i] <= 10^4
  • All values of nums are unique
  • nums is rotated at some pivot
  • -10^4 <= target <= 10^4

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Standard binary search O(log n) O(1) Only if array is not rotated
Modified BS (sorted half) O(log n) O(1) This problem — discard half each step
Find pivot + BS O(log n) O(1) Locate rotation index, then two BS calls
Linear scan O(n) O(1) Violates the O(log n) requirement

Thinking Process

Even after rotation, at least one half of the array (left or right of mid) remains sorted.

  1. Compute mid. If nums[mid] == target, return mid.
  2. If the left half [left … mid] is sorted (nums[left] <= nums[mid]):
    • Target lies in that sorted half iff nums[left] <= target < nums[mid] → shrink right; else shrink left.
  3. Otherwise the right half is sorted:
    • Target lies there iff nums[mid] < target <= nums[right] → shrink left; else shrink right.

This is the same binary-search loop — only the “which half to discard?” rule changes.

Rotated sorted array sorted half 4 5 6 7 pivot 0 1 2 One half is always sorted → BS on that half

Solution — O(log n) time, O(1) space

class Solution {
        public int search(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;
            }

            // Subarray on mid's left is sorted
            if (nums[mid] >= nums[left]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // Subarray on mid's right is sorted
            else {
                if (target <= nums[right] && target > nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}

Solution Explanation

Why one half is always sorted: In a rotated sorted array, walking from left to mid either stays inside the original ascending segment or crosses the pivot. If nums[mid] >= nums[left], no pivot lies between left and mid, so that segment is sorted. Otherwise the pivot is in the left part, so the right segment [mid … right] must be sorted.

Discard logic: On a sorted segment, binary search tells you whether target can exist there (compare target to segment bounds). If yes, search that half; if no, search the other half.

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

Step left right mid nums[mid] Sorted half Action
1 0 6 3 7 left [4,5,6,7] 0 not in [4,7) → left = 4
2 4 6 5 1 left [0,1] 0 in [0,1) → right = 4
3 4 4 4 0 — found at index 4

Time: O(log n) — halve search space each iteration · Space: O(1)

Common Mistakes

  • Using nums[mid] > nums[left] instead of >= — fails when left == mid (single-element half)
  • Checking target against nums[right] when the left half is sorted (compare against the sorted half only)
  • Forgetting distinct values — with duplicates use LC 81

Key Takeaways

  • Rotated sorted array = modified binary search, not a new algorithm
  • Ask: “Which side is sorted?” then apply normal BS range checks on that side
  • Same template covers LC 81 (with duplicates) and LC 153

References

Template Reference