Search in Rotated Sorted Array in DSA Go - Time & Space Complexity

Time Complexity: Search in Rotated Sorted Array

O(log n)

Understanding Time Complexity

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

How does the time to find the number grow as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := (left + right) / 2
        if nums[mid] == target {
            return mid
        }
        if nums[left] <= nums[mid] {
            if target >= nums[left] && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            if target > nums[mid] && 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 for loop that halves the search range each time.
• How many times: The loop 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.

Final Time Complexity

Time Complexity: O(log n)

This means the search time grows slowly, even if the list becomes very large.

Common Mistake

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

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

Interview Connect

Understanding this search helps you show how to handle tricky sorted data efficiently, a skill many interviews value.

Self-Check

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