Back to main article
LC 33 Classic variant Medium

Search in Rotated Sorted Array

Classic binary search adapted for a rotated array. The invariant: one half is always fully sorted — use that to decide where the target must be.

Problem

What are we solving?

Problem Statement

Given an integer array nums sorted in ascending order (with distinct values) that has been rotated at an unknown pivot, and an integer target, return the index of target or -1 if not present. Must run in O(log n).

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
Intuition

One half is always sorted — use it

A rotated sorted array is two sorted segments glued together. At any mid, either the left half or the right half is guaranteed to be fully sorted. Whichever is sorted, we can check in O(1) whether the target lies inside it.

Check which half is sorted. Check if the target belongs in it. If yes — search there. If no — search the other half. Repeat.

nums = [4, 5, 6, 7, 0, 1, 2] · target = 0
upper4
upper5
upper6
mid=37
target0
lower1
lower2
mid=7. Left half [4,5,6,7] is sorted. Is 0 in [4,7]? No → search right half.

Step-by-step walkthrough

1
left=0, right=6 → mid=3, nums[3]=7

nums[left]=4 <= nums[mid]=7 → left half [4..7] is sorted. Is target 0 in [4,7]? No → left = mid+1 = 4.

2
left=4, right=6 → mid=5, nums[5]=1

nums[left]=0 <= nums[mid]=1 → left half [0,1] is sorted. Is target 0 in [0,1]? Yes → right = mid-1 = 4.

3
left=4, right=4 → mid=4, nums[4]=0

nums[4] == target → return 4. Found!

Solution

Clean implementation

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;

            if (nums[left] <= nums[mid]) {        // left half is sorted
                if (target >= nums[left] && target < nums[mid])
                    right = mid - 1;              // target in left half
                else
                    left = mid + 1;               // target in right half
            } else {                              // right half is sorted
                if (target > nums[mid] && target <= nums[right])
                    left = mid + 1;               // target in right half
                else
                    right = mid - 1;              // target in left half
            }
        }
        return -1;
    }
}
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target: return mid

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

Complexity

Time
O(log n)
Still halves the search space each step despite the rotation.
Space
O(1)
Constant extra space — just pointers.
→

vs LC 153: LC 153 finds the pivot using First True. LC 33 doesn't need the pivot — it uses the sorted-half invariant directly to search for the target in one pass.

↑ Pattern map