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?"

Practice

1. What is the main challenge when searching in a rotated sorted array compared to a normal sorted array?

easy

A. The array contains only negative numbers

B. The array elements are all the same

C. The array is sorted in descending order

D. The array is split into two sorted parts, so normal binary search needs adjustment

Solution

1. Step 1: Understand the array structure

   A rotated sorted array is created by taking a sorted array and rotating it at some pivot, splitting it into two sorted parts.

2. Step 2: Reason about search difficulty

   Normal binary search assumes the whole array is sorted, but here the array is split, so we must adjust the search to handle two sorted parts.

3. Final Answer:

   The array is split into two sorted parts, so normal binary search needs adjustment -> Option D

4. Quick Check:

   Rotated array = split sorted parts [OK]

Hint: Look for the pivot splitting the array into two sorted halves [OK]

Common Mistakes:

• Assuming the entire array is sorted
• Ignoring the pivot point
• Using linear search instead of binary search

2. Which of the following is the correct syntax to start a binary search in a rotated sorted array in JavaScript?

easy

A. let left = 0, right = arr.length - 1;

B. let left = 1, right = arr.length;

C. let left = -1, right = arr.length;

D. let left = 0, right = arr.length;

Solution

1. Step 1: Identify valid index range for binary search

   Binary search uses zero-based indexing, so left starts at 0 and right at last index (length - 1).

2. Step 2: Check each option

   let left = 0, right = arr.length - 1; correctly sets left=0 and right=arr.length-1. Others have invalid ranges or off-by-one errors.

3. Final Answer:

   let left = 0, right = arr.length - 1; -> Option A

4. Quick Check:

   Index range = 0 to length-1 [OK]

Hint: Start binary search with left=0 and right=length-1 [OK]

Common Mistakes:

• Using right = arr.length (out of bounds)
• Starting left at 1 instead of 0
• Negative indices for left or right

3. What will be the output of the following code snippet?

const arr = [4,5,6,7,0,1,2];
function search(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 (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;
}
console.log(search(arr, 0));

medium

A. 6

B. 0

C. 4

D. -1

Solution

1. Step 1: Understand the array and target

   The array is rotated sorted: [4,5,6,7,0,1,2], target is 0.

2. Step 2: Trace the binary search steps

   Initial left=0, right=6, mid=3 (value 7). Left half is sorted (4 to 7). Target 0 is not in left half, so search right half: left=4, right=6.
   New mid=5 (value 1). Left half (0 to 1) is sorted. Target 0 is in left half, so right=4.
   New mid=4 (value 0), found target at index 4.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Target 0 found at index 4 [OK]

Hint: Check which half is sorted, then decide search side [OK]

Common Mistakes:

• Not updating left/right correctly
• Confusing sorted half
• Returning wrong index or -1

4. Identify the bug in this search function for rotated sorted array:

function search(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 (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;
}

medium

A. The loop condition should be left <= right, not left < right

B. The mid calculation is incorrect

C. The target comparison uses wrong operators

D. The function should return left instead of -1

Solution

1. Step 1: Analyze the loop condition

   The loop uses while(left < right), which misses checking when left equals right, possibly skipping the last element.

2. Step 2: Correct the loop condition

   Changing to while(left <= right) ensures all elements are checked, including when left == right.

3. Final Answer:

   The loop condition should be left <= right, not left < right -> Option A

4. Quick Check:

   Loop must cover all indices [OK]

Hint: Use while(left <= right) to cover all elements [OK]

Common Mistakes:

• Using while(left < right) misses last element
• Incorrect mid calculation (not here though)
• Returning wrong index when not found

5. Given a rotated sorted array with possible duplicates, which modification is needed in the binary search to correctly find the target?

const arr = [2,5,6,0,0,1,2];
function search(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return true;
    if (nums[left] === nums[mid] && nums[mid] === nums[right]) {
      left++;
      right--;
    } else 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 false;
}

hard

A. Remove the duplicate elements before searching

B. Add checks to skip duplicates when left, mid, right are equal

C. Use linear search instead of binary search

D. Ignore duplicates and proceed as normal

Solution

1. Step 1: Understand duplicates impact

   Duplicates can cause ambiguity in deciding which half is sorted, breaking normal binary search logic.

2. Step 2: Skip duplicates when left, mid, right are equal

   When nums[left] == nums[mid] == nums[right], increment left and decrement right to skip duplicates and reduce search space.

3. Final Answer:

   Add checks to skip duplicates when left, mid, right are equal -> Option B

4. Quick Check:

   Skip duplicates to maintain binary search correctness [OK]

Hint: Skip duplicates when left, mid, right values match [OK]

Common Mistakes:

• Ignoring duplicates causing infinite loops
• Trying to remove duplicates before search
• Switching to linear search unnecessarily