Search in Rotated Sorted Array

⚡ Difficulty: Medium 🏷️ Pattern: Modified Binary Search 🏢 Asked at: PhonePe, Amazon, Google, Microsoft

Problem

A sorted array was rotated at an unknown pivot (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Given the rotated array (distinct values) and a target, return its index or -1. Must run in O(log n).

Example:

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

Approach

One half is always sorted

After a single rotation, when you split at mid, at least one side (left..mid or mid..right) is fully sorted. Detect which, then check whether the target lies within that sorted side’s range:

• If yes, search that side.
• If no, search the other side.

Compare nums[left] with nums[mid]:

• nums[left] <= nums[mid] → left half is sorted.
• Otherwise → right half is sorted.

Standard binary search bookkeeping otherwise, halving the range each step.

Complexity

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

def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 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

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[left] <= nums[mid]) {            // left sorted
            if (nums[left] <= target && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else {                                 // right sorted
            if (nums[mid] < target && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

Try It Yourself

Write your solution and run it live in C++, Java, Python, Go, Rust, and more — right here in the browser.

Run your code to see output here.

Key Insight

Rotation breaks global order but preserves it locally: one half around mid is always sorted. Once you know which half is sorted, a simple range check tells you whether the target is inside it, so you can discard half the array each step — keeping the O(log n) guarantee.

Follow-ups

• Duplicates allowed? → LC 81: when nums[left] == nums[mid], you can’t tell which half is sorted — shrink left++; worst case O(n).
• Find minimum / pivot → LC 153: binary search for the rotation point.

Related Problems

• Find Minimum in Rotated Sorted Array
• Search in Rotated Sorted Array II
• Search in Rotated Sorted Array (LC 33)

Drop a comment below if you want the find-the-pivot walkthrough 👇