Binary Search Fundamentals — Search in Rotated Sorted Array

Picture this: you get handed an array [4, 5, 6, 7, 0, 1, 2] and asked to find 0. The interviewer says "must be O(log n)." You look at it — it's not sorted. You start to reach for a linear scan, then you notice: it's almost sorted. It's a sorted array that got rotated.

That's the interview moment this post is about. The array has structure you can exploit, and recognizing that structure is the whole game.

The Core Idea: One Half Is Always Sorted

Standard binary search works because you can always determine which half contains the target. In a fully sorted array, that's trivial: if target < nums[mid], go left; otherwise go right.

In a rotated array, you can't do that directly. But there's a key insight: no matter where you split a once-rotated sorted array, at least one of the two halves is always fully sorted.

Think about it. If you rotate [0, 1, 2, 4, 5, 6, 7] to get [4, 5, 6, 7, 0, 1, 2], any mid you pick creates one sorted half and one "wrapped" half. You just need to figure out which is which — and you can do that by comparing nums[mid] to nums[right].

• If nums[mid] > nums[right]: the right side contains the rotation point, so the left half is sorted
• If nums[mid] <= nums[right]: the left side contains the rotation point (or there's no rotation), so the right half is sorted

Once you know which half is sorted, you can check whether the target falls within that half's value range. If it does, search there. If not, search the other half.

Visualizing a Rotated Array Binary Search

Array: [4, 5, 6, 7, 0, 1, 2], target: 0

Three iterations. O(log n) with no preprocessing.

Problem 1: Search in Rotated Sorted Array (LeetCode 33)

Given a rotated sorted array with unique values and a target, return the index of the target or -1.

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0 Output: 4

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3 Output: -1

Brute Force: Linear Scan

// Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
// Output: 4
 
const searchBrute = (nums, target) => {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) return i;
  }
  return -1;
};
// Time: O(n) | Space: O(1)
// Correct but misses the O(log n) requirement

Works, but the interviewer will push back immediately. "Can you do better?" Yes — the array has structure.

Optimized: Modified Binary Search

// Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
// Output: 4
 
const search = (nums, target) => {
  let left = 0;
  let right = nums.length - 1;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (nums[mid] === target) return mid;
 
    // Determine which half is sorted by comparing mid to right
    if (nums[mid] > nums[right]) {
      // Left half [left..mid] is sorted
      if (nums[left] <= target && target < nums[mid]) {
        // Target is within the sorted left half
        right = mid - 1;
      } else {
        // Target must be in the right half
        left = mid + 1;
      }
    } else {
      // Right half [mid..right] is sorted
      if (nums[mid] < target && target <= nums[right]) {
        // Target is within the sorted right half
        left = mid + 1;
      } else {
        // Target must be in the left half
        right = mid - 1;
      }
    }
  }
 
  return -1;
};
// Time: O(log n) | Space: O(1)

Walk through the two branches:

Left half sorted (nums[mid] > nums[right]): The values go from nums[left] up to nums[mid] in order. Check nums[left] <= target < nums[mid]. If true, shrink right. If false, shrink left.

Right half sorted (nums[mid] <= nums[right]): The values go from nums[mid] up to nums[right] in order. Check nums[mid] < target <= nums[right]. If true, shrink left. If false, shrink right.

Problem 2: Find Minimum in Rotated Sorted Array (LeetCode 153)

Now we don't have a target. We just want the minimum element. Must run in O(log n).

Input: nums = [3, 4, 5, 1, 2] Output: 1

Input: nums = [4, 5, 6, 7, 0, 1, 2] Output: 0

The minimum is always the rotation point — the element just after the largest element in the array. It's where the array "wraps around."

// Input: nums = [3, 4, 5, 1, 2]
// Output: 1
 
const findMin = (nums) => {
  // If the array is already sorted (no rotation), minimum is first element
  if (nums[0] < nums[nums.length - 1]) return nums[0];
 
  let left = 0;
  let right = nums.length - 1;
 
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (nums[mid] > nums[right]) {
      // Minimum is in the right half (rotation point is right of mid)
      left = mid + 1;
    } else {
      // mid could be the minimum — don't exclude it
      right = mid;
    }
  }
 
  return nums[left]; // left === right === index of minimum
};
// Time: O(log n) | Space: O(1)

Notice the differences from Problem 1:

• Loop condition: left < right instead of left <= right
• Right pointer: right = mid instead of right = mid - 1

Both changes are intentional. We use left < right because we're converging to a single element (the minimum), not searching for a target. We use right = mid because mid itself might be the minimum — we never want to exclude it.

Problem 3: Search in Rotated Sorted Array II (LeetCode 81)

Same as Problem 1, but the array can have duplicates. Return true or false instead of an index.

Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 0 Output: true

Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 3 Output: false

Duplicates break the key check. If nums[mid] === nums[right], we can't tell which half is sorted. Example: [1, 0, 1, 1, 1] — nums[mid] === nums[right] === 1, but the left half is NOT sorted.

The fix: when nums[mid] === nums[right], we can't make a useful binary decision, so we shrink the window by one from the right.

// Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 0
// Output: true
 
const searchWithDuplicates = (nums, target) => {
  let left = 0;
  let right = nums.length - 1;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (nums[mid] === target) return true;
 
    // Can't determine which half is sorted — shrink window
    if (nums[mid] === nums[right]) {
      right--;
      continue;
    }
 
    if (nums[mid] > nums[right]) {
      // 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 false;
};
// Time: O(log n) average, O(n) worst case (all same elements)
// Space: O(1)

The worst case degrades to O(n) — imagine [1, 1, 1, 1, 1, 1, 0, 1]. Every iteration we can only shrink by one. That's the honest complexity to tell your interviewer.

Complexity Cheat Sheet

Interview Tips

Tip 1: Lead with "one half is always sorted." Say this before writing any code. It signals to the interviewer that you understand why the approach works, not just that you memorized it. Walk them through why this property holds — a single rotation means the unsorted segment is contiguous, so any split hits at most one unsorted boundary.

Tip 2: The right = mid vs right = mid - 1 distinction is a common source of bugs. When you're searching for a specific target and you know mid isn't the target (because nums[mid] !== target), use right = mid - 1. When you're converging to a minimum and mid could be the answer, use right = mid. Clarify this to yourself on the whiteboard before coding.

Tip 3: Always handle the no-rotation case explicitly for Find Minimum. if (nums[0] < nums[nums.length - 1]) return nums[0] is a one-liner that prevents edge case bugs and also communicates to the interviewer that you're thinking about the full input space, not just the "interesting" case.