Search in Rotated Sorted Array in DSA C++ - Time & Space Complexity

Time Complexity: Search in Rotated Sorted Array

O(log n)

Understanding Time Complexity

We want to know how fast we can find a number in a rotated sorted list.

How does the search time grow as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code searches for a target number in a rotated sorted array using a modified binary search.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that halves the search range each time.
• How many times: At most, it runs about log base 2 of n times, where n is the array size.

How Execution Grows With Input

Each step cuts the search area roughly in half, so the number of steps grows slowly as the list grows.

Input Size (n)	Approx. Operations
10	About 4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: Doubling the input size adds only one more step to the search.

Final Time Complexity

Time Complexity: O(log n)

This means the search time grows slowly, making it efficient even for large lists.

Common Mistake

[X] Wrong: "Because the array is rotated, we must check every element, so it is O(n)."

[OK] Correct: The code cleverly uses the sorted parts to skip half the array each time, keeping the search fast.

Interview Connect

Understanding this search shows you can adapt classic methods to tricky situations, a skill valued in problem solving.

Self-Check

"What if the array was not rotated but still sorted? How would the time complexity change?"