Search in Rotated Sorted Array

Flipkart

Array

Binary Search

There is an integer array nums sorted in ascending order (with distinct values), which is possibly rotated at an unknown pivot. Given the array and an integer target, return the index of target if it is in nums, or -1 if it is not.

You must write an algorithm with O(log n) runtime complexity.

Example:

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

Solution Walkthrough

A plain Binary Search assumes the whole array is sorted, which isn't true here — but at every step, at least one half of the current search range is guaranteed to be sorted. The trick is to detect which half is sorted and check whether the target falls inside it.

Use the standard low/high/mid setup from Binary Search.
If nums[mid] === target, return mid.
Determine which half is sorted by comparing nums[low] and nums[mid]:
- If nums[low] <= nums[mid], the left half is sorted. If target falls within [nums[low], nums[mid]), search left (high = mid - 1); otherwise search right (low = mid + 1).
- Otherwise the right half is sorted. If target falls within (nums[mid], nums[high]], search right; otherwise search left.
Repeat until low > high, at which point the target isn't present — return -1.

Each step still halves the search space, so this remains O(log n) time and O(1) space, just like standard Binary Search.

function search(nums, target) {
    let low = 0, high = nums.length - 1;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (nums[mid] === target) return mid;

        if (nums[low] <= nums[mid]) {
            // Left half [low, mid] is sorted
            if (nums[low] <= target && target < nums[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        } else {
            // Right half [mid, high] is sorted
            if (nums[mid] < target && target <= nums[high]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }

    return -1;
}

Related Algorithms

Binary Search →