Search in Rotated Sorted Array in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of search in rotated sorted array

What is the output of the following JavaScript code that searches for a target in a rotated sorted array?

DSA Javascript

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

console.log(search([4,5,6,7,0,1,2], 0));

A 0

B 6

C -1

D 4

💡 Hint

Think about how the rotated sorted array is split and how binary search adapts.

The target 0 is at index 4 in the rotated array [4,5,6,7,0,1,2]. The search function correctly finds and returns index 4.

❓ Predict Output

intermediate

Output when target is not in rotated sorted array

What is the output of this code when the target is not present in the rotated sorted array?

DSA Javascript

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

console.log(search([4,5,6,7,0,1,2], 3));

A -1

B 2

C 0

D 6

💡 Hint

If the target is not found, what does the function return?

The target 3 is not in the array, so the function returns -1 indicating not found.

🧠 Conceptual

advanced

Why binary search works on rotated sorted arrays

Why can binary search be adapted to work on a rotated sorted array?

A Because the array elements are all unique, so we can search linearly.

B Because the array is fully sorted, so normal binary search applies without changes.

C Because at least one half of the array is always sorted, allowing us to decide which half to search next.

D Because the rotation does not affect the order of elements, so we can ignore it.

💡 Hint

Think about how the array is split by the rotation point.

In a rotated sorted array, one half is always sorted. This property lets us decide which half to discard and which to keep searching, adapting binary search.

🔧 Debug

advanced

Identify the error in this rotated array search code

What error will this code produce when searching in a rotated sorted array?

DSA Javascript

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

console.log(search([4,5,6,7,0,1,2], 0));

A Returns -1 even if target is present

B SyntaxError due to missing parentheses

C Infinite loop because left and right pointers never meet

D Returns correct index 4

💡 Hint

Check the loop condition and how it affects the search range.

Using 'while (left < right)' misses the case when left equals right, so the target at that position is never checked, causing a wrong -1 return.

🚀 Application

expert

Find minimum element in rotated sorted array

Given a rotated sorted array with no duplicates, which code correctly finds the minimum element?

A

function findMin(nums) {
  let min = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < min) min = nums[i];
  }
  return min;
}

B

function findMin(nums) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return nums[left];
}

C

function findMin(nums) {
  return Math.min(...nums);
}

D

function findMin(nums) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] < nums[left]) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return nums[left];
}

💡 Hint

Use binary search logic to find the point where order breaks.

Option B uses binary search to find the minimum by comparing mid and right elements, narrowing the search space efficiently.

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