Search in Rotated Sorted Array in DSA Javascript - 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. This helps us understand the cost of searching when the list is not fully sorted.

The question is: How does the search time grow as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function searchRotatedArray(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 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: The loop runs until the search range is empty, roughly halving the size each time.

How Execution Grows With Input

Each step cuts the list 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, showing slow growth.

Final Time Complexity

Time Complexity: O(log n)

This means the search time grows very slowly even if the list gets much bigger, because we cut the search area in half each step.

Common Mistake

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

[OK] Correct: The code cleverly uses the sorted parts to decide which half to search next, so it still works in logarithmic time.

Interview Connect

Understanding this search method shows you can adapt classic techniques to tricky situations, a skill valued in problem solving and interviews.

Self-Check

"What if the array was not rotated but had duplicates? How would the time complexity change?"