Search in a Rotated Sorted Array

A sorted array that has been rotated — cut at some pivot point and the two halves swapped — is no longer globally sorted. A naive binary search breaks because the midpoint comparison no longer reliably tells you which direction to go. However, one key observation saves the algorithm: at least one of the two halves [lo, mid] or [mid, hi] is always fully sorted, and you can detect which one in O(1) by comparing arr[lo] with arr[mid].

The Core Insight

Consider [4, 5, 6, 7, 0, 1, 2]. If mid lands at index 3 (arr[mid] = 7):

• arr[lo] (4) <= arr[mid] (7) — the left half [4, 5, 6, 7] is sorted.
• Use standard binary search logic to ask: is the target in [arr[lo], arr[mid]]?
  • If yes, search left (hi = mid - 1).
  • If no, search right (lo = mid + 1).

If arr[lo] > arr[mid], the right half is the sorted one. Apply the same check against [arr[mid], arr[hi]].

Invariant

At every step, either:

1. The left half [lo..mid] is sorted and the target is or is not inside it, or
2. The right half [mid..hi] is sorted and the same check applies.

The window shrinks by at least half on every iteration, preserving O(log n).

Implementation

function searchRotated(arr, target) {
  let lo = 0;
  let hi = arr.length - 1;

  while (lo <= hi) {
    const mid = Math.floor(lo + (hi - lo) / 2);

    if (arr[mid] === target) return mid;

    // Determine which half is sorted
    if (arr[lo] <= arr[mid]) {
      // Left half [lo..mid] is sorted
      if (arr[lo] <= target && target < arr[mid]) {
        hi = mid - 1; // target is in the sorted left half
      } else {
        lo = mid + 1; // target must be in the right half
      }
    } else {
      // Right half [mid..hi] is sorted
      if (arr[mid] < target && target <= arr[hi]) {
        lo = mid + 1; // target is in the sorted right half
      } else {
        hi = mid - 1; // target must be in the left half
      }
    }
  }

  return -1;
}

searchRotated([4, 5, 6, 7, 0, 1, 2], 0); // 4
searchRotated([4, 5, 6, 7, 0, 1, 2], 3); // -1
searchRotated([1], 0);                    // -1

Complexity

Handling Duplicates

When duplicates are present, arr[lo] === arr[mid] does not tell you which half is sorted. The safe fallback is to increment lo and retry, which degrades worst-case performance to O(n) but keeps the algorithm correct.

function searchRotatedWithDups(arr, target) {
  let lo = 0;
  let hi = arr.length - 1;

  while (lo <= hi) {
    const mid = Math.floor(lo + (hi - lo) / 2);

    if (arr[mid] === target) return mid;

    // Ambiguous: arr[lo] === arr[mid] — cannot determine sorted half
    if (arr[lo] === arr[mid]) {
      lo++;
      continue;
    }

    if (arr[lo] < arr[mid]) {
      if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
      else                                        lo = mid + 1;
    } else {
      if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
      else                                        hi = mid - 1;
    }
  }

  return -1;
}

Finding the Pivot Index

A related problem is finding the pivot (the index of the minimum element) in a rotated sorted array. Apply the same “which half is sorted” logic: if arr[mid] < arr[hi], the minimum is in [lo, mid]; otherwise it is in [mid + 1, hi]. This runs in O(log n) and the resulting pivot index can then be used to offset binary searches into the original sorted order.

Up Next

Now that you have a thorough grounding in searching algorithms, the next section explores tree-based data structures that enable even more powerful search and retrieval patterns.