Search in Rotated Sorted Array

Practice Here

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 &lt;= 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.

Brute Force: Linear Search#

Scan every element linearly and return the index on a match. This completely ignores the sorted (and rotated) structure of the array, so it runs in O(n) — correct but far from optimal.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();

        for(int i=0;i<n;i++)
        {
            if(nums[i]==target)
                return i;
        }
        return -1;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)

Better Approach: Binary Search#

Even after rotation, one of the two halves around mid is always fully sorted — we exploit this to decide which half to discard. If the target falls within the sorted half's bounds, we search there; otherwise we discard that half and search the other. This preserves the O(log n) halving property despite the rotation.

• Rotated Array Always Has One Sorted Half
• If the start ≤ mid, then left half is sorted.
  • Now check whether the target lies in the left sorted half
• If the left half isn’t sorted, the right half must be sorted.
  • Similarly, check if target lies in the right sorted half and adjust search bounds accordingly.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();

        int start =0, end = n-1;
        while(start<=end)
        {
            int mid = start + (end-start)/2;

            if(nums[mid]==target)
                return mid;

            else if(nums[start] <= nums[mid]) //left half sorted
            {
                if(nums[start] <= target && target <= nums[mid])
                    end = mid-1;
                else
                    start = mid+1;
            }
            else //right half sorted
            {
                if(nums[mid] <= target && target <= nums[end])
                    start = mid+1;
                else
                    end = mid-1;
            }

        }
        return -1;
    }
};

Time Complexity: O(log n)

Space Complexity: O(1)

Follow Up#

How would your logic need to change if the array contained duplicate values instead of unique ones?#

With duplicates, the key invariant breaks down: when nums[start] == nums[mid], you can no longer tell which half is sorted. For example, [3, 1, 2, 3, 3] — at start=0, mid=2, both values are 3, so the left half looks "sorted" but the right does too.

The fix: add a third branch to handle the ambiguous case — when nums[start] == nums[mid] (and optionally nums[mid] == nums[end]), just shrink both pointers by one (start++, end--) and continue. This safely skips the duplicates without losing the target.

// With duplicates (LeetCode #81)
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int start = 0, end = nums.size() - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] == target) return true;

            // Can't determine sorted half — shrink both ends
            if (nums[start] == nums[mid] && nums[mid] == nums[end]) {
                start++;
                end--;
            } else if (nums[start] <= nums[mid]) { // left half sorted
                if (nums[start] <= target && target < nums[mid])
                    end = mid - 1;
                else
                    start = mid + 1;
            } else { // right half sorted
                if (nums[mid] < target && target <= nums[end])
                    start = mid + 1;
                else
                    end = mid - 1;
            }
        }
        return false;
    }
};

Trade-off: In the worst case (e.g. all duplicates), the start++/end-- fallback degrades to O(n). The average case is still O(log n) when duplicates are sparse. This is exactly Search in Rotated Sorted Array II.