Search in Rotated Sorted Array in DSA Javascript

Mental Model

We want to find a number in a list that was sorted but then rotated. We use a smart search that checks which part is sorted to decide where to look next.

Analogy: Imagine a clock face with numbers 1 to 12 in order, but someone turned the clock so 3 is now at the top. To find a number, you check which side of the clock is still in order and decide where to look.

Original sorted array:
[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> null
Rotated array (rotated at 4):
[5] -> [6] -> [7] -> [1] -> [2] -> [3] -> [4] -> null
↑ start pointer
               ↑ mid pointer
                           ↑ end pointer

Dry Run Walkthrough

Input: array: [5,6,7,1,2,3,4], target: 3

Goal: Find the index of target 3 in the rotated sorted array

Step 1: Set start=0, end=6, mid=(0+6)//2=3, check value at mid=1

[5] -> [6] -> [7] -> [1] -> [2] -> [3] -> [4] -> null
start=0 (5), mid=3 (1), end=6 (4)

Why: We start searching in the whole array by checking the middle element

Step 2: Check which half is sorted: left side [5,6,7] or right side [1,2,3,4]

[5] -> [6] -> [7] -> [1] -> [2] -> [3] -> [4] -> null
start=0 (5), mid=3 (1), end=6 (4)

Why: Left half is not sorted because 5 > 1, right half is sorted because 1 <= 4

Step 3: Target 3 is between mid=1 and end=4, so search right half: start=mid+1=4

[5] -> [6] -> [7] -> [1] -> [2] -> [3] -> [4] -> null
start=4 (2), end=6 (4)

Why: Since target is in sorted right half, we discard left half

Step 4: Calculate mid=(4+6)//2=5, check value at mid=3

[5] -> [6] -> [7] -> [1] -> [2] -> [3] -> [4] -> null
start=4 (2), mid=5 (3), end=6 (4)

Why: Check middle of new search range

Step 5: Found target at mid=5, return index 5

[5] -> [6] -> [7] -> [1] -> [2] -> [3] -> [4] -> null
index=5

Why: Target found, search ends

Result:

[5] -> [6] -> [7] -> [1] -> [2] -> [3] -> [4] -> null
Target 3 found at index 5

Annotated Code

DSA Javascript

class RotatedSortedArray {
  constructor(arr) {
    this.arr = arr;
  }

  search(target) {
    let start = 0;
    let end = this.arr.length - 1;

    while (start <= end) {
      const mid = Math.floor((start + end) / 2);
      if (this.arr[mid] === target) {
        return mid; // found target
      }

      // Check if left half is sorted
      if (this.arr[start] <= this.arr[mid]) {
        // Target in left half?
        if (this.arr[start] <= target && target < this.arr[mid]) {
          end = mid - 1; // search left half
        } else {
          start = mid + 1; // search right half
        }
      } else {
        // Right half is sorted
        if (this.arr[mid] < target && target <= this.arr[end]) {
          start = mid + 1; // search right half
        } else {
          end = mid - 1; // search left half
        }
      }
    }
    return -1; // target not found
  }
}

// Driver code
const arr = [5,6,7,1,2,3,4];
const target = 3;
const rsa = new RotatedSortedArray(arr);
const index = rsa.search(target);
if (index !== -1) {
  console.log(`Target ${target} found at index ${index}`);
} else {
  console.log(`Target ${target} not found`);
}

const mid = Math.floor((start + end) / 2);

Calculate middle index to split search range

if (this.arr[mid] === target) { return mid; }

Check if middle element is the target

if (this.arr[start] <= this.arr[mid]) {

Check if left half is sorted

if (this.arr[start] <= target && target < this.arr[mid]) { end = mid - 1; } else { start = mid + 1; }

Decide to search left or right half based on target position in sorted left half

else { if (this.arr[mid] < target && target <= this.arr[end]) { start = mid + 1; } else { end = mid - 1; } }

Right half is sorted; decide where target lies and adjust search range

Output

Target 3 found at index 5

Complexity Analysis

Time: O(log n) because each step halves the search range by checking sorted halves

Space: O(1) because we use only a few variables, no extra space proportional to input

vs Alternative: Compared to linear search O(n), this binary search approach is much faster on large arrays

Edge Cases

Empty array

Returns -1 immediately because start > end

DSA Javascript

while (start <= end) {

Array with one element equal to target

Returns index 0 immediately

DSA Javascript

if (this.arr[mid] === target) { return mid; }

Target not in array

Returns -1 after search range is exhausted

DSA Javascript

return -1; // target not found

When to Use This Pattern

When you see a sorted array that has been rotated and need to find an element quickly, use this pattern to adapt binary search by checking which half is sorted.

Common Mistakes

Mistake: Not checking which half is sorted before deciding where to search next
Fix: Always check if left half or right half is sorted to correctly narrow search range

Mistake: Using <= or < incorrectly causing infinite loops or wrong index
Fix: Use strict inequalities carefully to avoid missing the target or infinite loops

Summary

Finds a target value in a rotated sorted array efficiently using modified binary search.

Use when you have a sorted array rotated at some pivot and need fast search.

The key is to identify which half is sorted to decide where to continue searching.

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