Search in Rotated Sorted Array in DSA Javascript - Build from Scratch

Search in Rotated Sorted Array

📖 Scenario: Imagine you have a list of numbers that was originally sorted from smallest to largest. But then, someone took a part of the list from the front and moved it to the end. This is called a rotated sorted array.For example, the list [1, 2, 3, 4, 5] might become [3, 4, 5, 1, 2] after rotation.

🎯 Goal: You will write a program to find the position of a number in this rotated list. If the number is not in the list, your program should say it is not found.

📋 What You'll Learn

Create an array called rotatedArray with exact numbers given.

Create a variable called target to hold the number to find.

Write a function called searchRotatedArray that finds the index of target in rotatedArray using a smart search.

Print the index found or -1 if the number is not in the array.

💡 Why This Matters

🌍 Real World

Rotated sorted arrays appear in systems where data is shifted or rotated for performance or storage reasons, like in circular buffers or time-based logs.

💼 Career

Understanding how to search efficiently in rotated sorted arrays is useful for software engineers working on search algorithms, database indexing, and system optimizations.

1

Create the rotated sorted array

Create an array called rotatedArray with these exact numbers in order: 15, 18, 2, 3, 6, 12

DSA Javascript

// Your code here

Hint

Use square brackets [] to create the array and separate numbers with commas.

2

Set the target number to find

Create a variable called target and set it to the number 3

DSA Javascript

const rotatedArray = [15, 18, 2, 3, 6, 12];
// Your code here

Hint

Use const to create the variable and assign the number 3.

3

Write the search function for rotated sorted array

Write a function called searchRotatedArray that takes arr and target as inputs and returns the index of target in arr. Use a while loop with variables left and right to do a smart search in the rotated array.

DSA Javascript

const rotatedArray = [15, 18, 2, 3, 6, 12];
const target = 3;

// Write searchRotatedArray function here
// Your code here

Hint

Use binary search logic but adjust the left and right pointers based on which side is sorted.

4

Print the index of the target

Use console.log to print the result of calling searchRotatedArray with rotatedArray and target.

DSA Javascript

const rotatedArray = [15, 18, 2, 3, 6, 12];
const target = 3;

function searchRotatedArray(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left = arr[left] && target  arr[mid] && target <= arr[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

// Print the index of target
// Your code here

Hint

Call the function with rotatedArray and target and print the result.

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