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.