Solving Search in Rotated Array in JavaScript: Step-by-Step Guide

Introduction to Search in Rotated Sorted Array

The "Search in Rotated Sorted Array" problem is one of the most classic algorithmic challenges you'll encounter in coding interviews and real-world applications. It asks a deceptively simple question: given a sorted array that has been rotated at an unknown pivot, how do you efficiently find a target value?

A rotated array is created when you take a sorted array and shift its elements circularly. For example, the sorted array [0, 1, 2, 3, 4, 5, 6, 7] rotated at pivot index 3 becomes [4, 5, 6, 7, 0, 1, 2, 3]. Notice that the array is no longer fully sorted, but it retains a partial ordering that we can exploit.

Why This Problem Matters

This problem matters because it tests your understanding of binary search beyond its textbook form. Standard binary search assumes a fully sorted array, but real-world data is rarely so cooperative. Rotated arrays appear in:

• Circular buffers used in streaming applications and embedded systems
• Log files where timestamps wrap around midnight or across days
• Load balancers that distribute requests in a round-robin fashion
• Cache eviction systems that rotate entries
• Interview settings where it's a staple at companies like Google, Amazon, and Meta

The key insight is that even though the array is rotated, one half of the array (either the left or right portion from the midpoint) will always remain sorted. By identifying which half is sorted, you can determine whether your target lies within that half or the other, allowing you to discard half the search space each iteration.

Understanding the Problem Statement

Let's formalize the problem. You are given:

• An array of integers that was originally sorted in ascending order and then rotated at some unknown pivot index.
• A target integer value to search for.

You must return the index of the target if it exists in the array, or -1 if it does not. The optimal solution should run in O(log n) time complexity, which rules out a simple linear scan.

Consider these examples:

• Array: [4, 5, 6, 7, 0, 1, 2], Target: 0 → Output: 4
• Array: [4, 5, 6, 7, 0, 1, 2], Target: 3 → Output: -1
• Array: [1], Target: 0 → Output: -1

It's also worth noting that there is a variant of this problem where the array may contain duplicates. That variant is harder because duplicates can make it impossible to determine which half is sorted in O(log n) worst-case time, degrading to O(n). We'll focus on the distinct-values version first and address duplicates later.

The Naive Approach: Linear Search

Before diving into the optimal solution, let's look at the naive approach. A linear search simply iterates through every element until it finds the target or reaches the end of the array.

function linearSearch(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) {
      return i;
    }
  }
  return -1;
}

// Example usage
const nums = [4, 5, 6, 7, 0, 1, 2];
console.log(linearSearch(nums, 0)); // Output: 4
console.log(linearSearch(nums, 3)); // Output: -1

While this works and is easy to understand, it runs in O(n) time. For large arrays, this becomes a performance bottleneck. The problem explicitly demands O(log n) time, which means we need a binary search approach.

The Optimal Approach: Modified Binary Search

The breakthrough insight is that when you examine the middle element of a rotated sorted array, at least one of the two halves (left or right) will always be sorted. Here's the reasoning:

• If nums[mid] >= nums[left], then the left half is sorted.
• Otherwise, the right half must be sorted.

Once you know which half is sorted, you can check whether the target falls within that sorted half's range. If it does, search that half; otherwise, search the other half. This allows you to eliminate half the elements with each step, achieving O(log n) complexity.

Step-by-Step Algorithm

Let's break down the algorithm into clear steps:

• Initialize two pointers: left at index 0 and right at the last index.
• While left <= right, compute the middle index mid.
• If nums[mid] === target, return mid — you've found the target.
• Determine which half is sorted by comparing nums[mid] with nums[left].
• If the left half is sorted, check if the target is within [nums[left], nums[mid]). If yes, search the left half; otherwise, search the right half.
• If the right half is sorted, check if the target is within (nums[mid], nums[right]]. If yes, search the right half; otherwise, search the left half.
• If the loop ends without finding the target, return -1.

Implementing the Solution

Here's the complete implementation in JavaScript:

function searchRotatedArray(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    // Found the target
    if (nums[mid] === target) {
      return mid;
    }

    // Check if the left half is sorted
    if (nums[left] <= nums[mid]) {
      // Target is in the sorted left half
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // Right half is sorted
      // Target is in the sorted right half
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}

// Test cases
console.log(searchRotatedArray([4, 5, 6, 7, 0, 1, 2], 0)); // Output: 4
console.log(searchRotatedArray([4, 5, 6, 7, 0, 1, 2], 3)); // Output: -1
console.log(searchRotatedArray([1], 0)); // Output: -1
console.log(searchRotatedArray([1, 3], 3)); // Output: 1
console.log(searchRotatedArray([5, 1, 3], 5)); // Output: 0

Notice the use of <= in the condition nums[left] <= nums[mid]. This handles the edge case where left and mid point to the same element, which happens when the search space narrows to one or two elements.

Tracing Through an Example

To solidify your understanding, let's trace through the algorithm with the array [4, 5, 6, 7, 0, 1, 2] and target 0:

Iteration 1: left = 0, right = 6, mid = 3. nums[mid] = 7, which is not the target. Since nums[left] = 4 <= nums[mid] = 7, the left half is sorted. Is 0 in [4, 7)? No, because 0 < 4. So we search the right half: left = 4.

Iteration 2: left = 4, right = 6, mid = 5. nums[mid] = 1, not the target. Since nums[left] = 0 <= nums[mid] = 1, the left half is sorted. Is 0 in [0, 1)? Yes, because 0 >= 0 and 0 < 1. So we search the left half: right = 4.

Iteration 3: left = 4, right = 4, mid = 4. nums[mid] = 0, which equals the target. Return 4.

The algorithm found the target in just 3 iterations instead of scanning through up to 7 elements. For an array of one million elements, binary search would need only about 20 comparisons.

Handling Duplicates in the Array

The variant with duplicates introduces a tricky edge case. Consider the array [2, 2, 2, 3, 2, 2, 2] with target 3. When nums[left] === nums[mid] === nums[right], you cannot determine which half is sorted. In this situation, you must shrink the search space by moving both pointers inward until you can make a determination.

function searchRotatedArrayWithDuplicates(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (nums[mid] === target) {
      return mid;
    }

    // Handle the ambiguous case where we can't determine the sorted half
    if (nums[left] === nums[mid] && nums[mid] === nums[right]) {
      left++;
      right--;
    } else if (nums[left] <= nums[mid]) {
      // Left half is sorted
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // Right half is sorted
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}

// Test cases with duplicates
console.log(searchRotatedArrayWithDuplicates([2, 2, 2, 3, 2, 2, 2], 3)); // Output: 3
console.log(searchRotatedArrayWithDuplicates([1, 0, 1, 1, 1], 0)); // Output: 1

Be aware that in the worst case (an array of all identical elements except one), this degrades to O(n) time complexity because you may have to scan nearly every element. This is an inherent limitation — no algorithm can do better in the worst case when duplicates obscure the sorted structure.

Finding the Rotation Pivot

A closely related problem is finding the pivot index where the array was rotated. This is useful when you need to understand the structure of the array before searching. The pivot is the index of the smallest element in the array.

function findPivot(nums) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (nums[mid] > nums[right]) {
      // Pivot is in the right half
      left = mid + 1;
    } else {
      // Pivot is in the left half (including mid)
      right = mid;
    }
  }

  return left;
}

// Test cases
console.log(findPivot([4, 5, 6, 7, 0, 1, 2])); // Output: 4
console.log(findPivot([1, 2, 3, 4, 5])); // Output: 0 (not rotated)
console.log(findPivot([2, 1])); // Output: 1

Once you know the pivot, you could perform two separate binary searches: one on the left sorted portion and one on the right. However, the single-pass modified binary search we implemented earlier is more elegant and efficient.

Recursive Implementation

For those who prefer a recursive style, here's an equivalent implementation. The logic is identical, but the search space is narrowed through recursive calls rather than loop iterations.

function searchRotatedArrayRecursive(nums, target) {
  function helper(left, right) {
    if (left > right) {
      return -1;
    }

    const mid = Math.floor((left + right) / 2);

    if (nums[mid] === target) {
      return mid;
    }

    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) {
        return helper(left, mid - 1);
      } else {
        return helper(mid + 1, right);
      }
    } else {
      if (nums[mid] < target && target <= nums[right]) {
        return helper(mid + 1, right);
      } else {
        return helper(left, mid - 1);
      }
    }
  }

  return helper(0, nums.length - 1);
}

console.log(searchRotatedArrayRecursive([4, 5, 6, 7, 0, 1, 2], 0)); // Output: 4

Both iterative and recursive versions have the same O(log n) time complexity. The iterative version is generally preferred in production code because it avoids the overhead of function call stack growth and eliminates any risk of stack overflow for very large arrays.

Best Practices and Common Pitfalls

When implementing this algorithm, keep these best practices in mind:

• Use <= not < when comparing nums[left] with nums[mid]. Using strict less-than will fail on edge cases where left and mid coincide.
• Handle empty arrays at the start. If nums.length === 0, return -1 immediately to avoid undefined behavior.
• Use Math.floor for midpoint calculation. JavaScript does not have integer division, so (left + right) / 2 can produce a decimal. Alternatively, use (left + right) >> 1 for a faster bitwise floor.
• Watch for integer overflow in other languages. In JavaScript, numbers are 64-bit floats, so overflow isn't a concern, but in languages like Java or C++, use left + (right - left) / 2 instead of (left + right) / 2.
• Test edge cases thoroughly: single-element arrays, two-element arrays, non-rotated arrays, and targets at the pivot boundary.

Here's a more robust version with input validation:

function searchRotatedArrayRobust(nums, target) {
  if (!Array.isArray(nums) || nums.length === 0) {
    return -1;
  }

  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = (left + right) >> 1;

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

Performance Analysis

Let's analyze the time and space complexity of our solution:

• Time Complexity (distinct values): O(log n) — each iteration halves the search space.
• Time Complexity (with duplicates, worst case): O(n) — when most elements are identical, the pointer-shrinking step may process nearly every element.
• Space Complexity (iterative): O(1) — only a few variables are used regardless of input size.
• Space Complexity (recursive): O(log n) — the call stack grows proportionally to the depth of the recursion.

For a practical benchmark, here's a simple performance test comparing linear search with binary search on a large rotated array:

function benchmark() {
  const size = 10000000;
  const pivot = 3000000;
  const nums = [];

  // Build a rotated sorted array
  for (let i = 0; i < size - pivot; i++) {
    nums.push(pivot + i);
  }
  for (let i = 0; i < pivot; i++) {
    nums.push(i);
  }

  const target = nums[size - 1];

  // Linear search benchmark
  const startLinear = performance.now();
  linearSearch(nums, target);
  const endLinear = performance.now();

  // Binary search benchmark
  const startBinary = performance.now();
  searchRotatedArrayRobust(nums, target);
  const endBinary = performance.now();

  console.log(`Linear search: ${(endLinear - startLinear).toFixed(2)} ms`);
  console.log(`Binary search: ${(endBinary - startBinary).toFixed(2)} ms`);
}

benchmark();

On a typical machine, the binary search will complete in under a millisecond while the linear search may take tens of milliseconds — a dramatic difference that grows with array size.

Real-World Applications

Beyond interview preparation, the rotated array search pattern appears in several practical scenarios:

• Database systems that use log-structured merge trees may store sorted runs that have been rotated due to compaction.
• Distributed systems use consistent hashing with virtual nodes, creating a ring structure that is essentially a rotated sorted array of node positions.
• GPS and mapping applications store circular route data where the starting point may vary, creating a rotated sequence of coordinates.
• Financial applications track rolling time windows of stock prices, where the data wraps around trading day boundaries.

Understanding this algorithm also builds a foundation for more advanced topics like searching in bitonic arrays, finding peaks in mountain arrays, and solving problems on circular data structures.

Conclusion

The Search in Rotated Sorted Array problem is a powerful demonstration of how binary search can be adapted to work on data that isn't perfectly sorted. By recognizing that at least one half of a rotated array is always sorted, you can maintain the O(log n) efficiency that makes binary search so valuable. The key takeaways are identifying the sorted half at each step, correctly bounding the target within that half, and handling edge cases like duplicates and small arrays. Whether you're preparing for a coding interview or building a system that deals with circular or wrapped data, mastering this technique will make you a more versatile and effective JavaScript developer. Practice implementing both the iterative and recursive versions, test against edge cases, and you'll be well-equipped to tackle this problem and its many variants with confidence.