Binary Search crash course ↗ · 24

33. Search in Rotated Sorted Array

A sorted array rotated at an unknown pivot always has one sorted half — identify it first, then check if the target lies within it to halve the search space, achieving O(log n) even without knowing where the rotation is.

● MediumBinary SearchTypeScript

PROBLEM What we're solving

Given a sorted array of distinct integers rotated at some pivot (e.g. [4,5,6,7,0,1,2]), find the index of target in O(log n) time, or return -1 if it is not present. For example, nums=[4,5,6,7,0,1,2], target=0 → 4; target=3 → -1.

KEY IDEA One half is always fully sorted

Insight → even after rotation, splitting at mid always leaves at least one half that is contiguously sorted. Compare nums[lo] with nums[mid]: if nums[lo] ≤ nums[mid], the left half is sorted; otherwise the right half is sorted. Once you know which half is sorted, a simple range check tells you whether target lives there — if yes, search that half; if no, search the other.

RECIPE Sorted-half binary search

  • 0 · Standard setup. lo=0, hi=n-1. Loop while lo ≤ hi.
  • 1 · Check mid. If nums[mid] === target return mid.
  • 2 · Identify the sorted half. nums[lo] ≤ nums[mid] → left half is sorted; otherwise right half is sorted.
  • 3 · Range-check target against the sorted half.If target is inside the sorted half's range, move the pointer to search that half; otherwise move the other pointer to search the unsorted half.
  • 4 · Exhausted? Return -1. Loop ends without a match.
Classic confusion → using < instead of ≤ when checking nums[lo] ≤ nums[mid]. When lo === mid (two-element window) you must treat the left half as sorted. The = is load-bearing.

COST Complexity & alternatives

Linear scan
O(n)
Ignore the structure; iterate every element.
Sorted-half binary search
O(log n)
O(1) space; exploits at-least-one-sorted-half invariant.

The rotation does not change the search space halving — we eliminate half the elements at every step just as in regular binary search. Space is O(1): only two pointers.

Pattern transfer →this "identify sorted half first" logic extends directly to Search in Rotated Sorted Array II (with duplicates — the tricky case when nums[lo] === nums[mid] forces a linear fallback) and Find Minimum in Rotated Sorted Array (find the pivot instead of a target).

RUN IT Find the sorted half first, then decide

step 0 / 5
STARTSearch for 0 in rotated array [4, 5, 6, 7, 0, 1, 2]. Set lo=0, hi=6.
1function search(nums: number[], target: number): number {
2▶  let lo = 0;
3▶  let hi = nums.length - 1;
4 
5  while (lo <= hi) {
6    const mid = Math.floor((lo + hi) / 2);
7    if (nums[mid] === target) return mid;
8 
9    // Determine which half is sorted
10    if (nums[lo] <= nums[mid]) {
11      // Left half [lo..mid] is sorted
12      if (nums[lo] <= target && target < nums[mid]) {
13        hi = mid - 1;   // target in left sorted half
14      } else {
15        lo = mid + 1;   // target must be in right half
16      }
17    } else {
18      // Right half [mid..hi] is sorted
19      if (nums[mid] < target && target <= nums[hi]) {
20        lo = mid + 1;   // target in right sorted half
21      } else {
22        hi = mid - 1;   // target must be in left half
23      }
24    }
25  }
26 
27  return -1;
28}
nums40516273041526
State
0
lo
—
mid
6
hi
—
nums[mid]
0
target
lomidhifoundnot found
slowfast

TYPESCRIPT The solution, annotated

searchRotated.ts
function search(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length - 1;

  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] === target) return mid;

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

  return -1;
}

Reading it block by block

Lines 2–3 — initialise pointers. Standard binary search setup: lo=0, hi=n-1, loop while the window is non-empty.
Line 6 — early return. If nums[mid] is the target we are done. Always check this before the sorted-half logic.
Line 9 — identify the sorted half. nums[lo] ≤ nums[mid] means the left half has no wraparound — it is fully ascending. The = is essential: when the window is two elements, lo === mid and we must count the left half as sorted.
Lines 10–13 — target in sorted left half? Check if target falls in [nums[lo], nums[mid]). If yes, cut the right half away (hi = mid - 1); otherwise the target must be right of the pivot (lo = mid + 1).
Lines 15–20 — right half is sorted. Mirror logic: check if target falls in (nums[mid], nums[hi]]. If yes, advance lo = mid + 1; otherwise the target is in the left (possibly rotated) portion (hi = mid - 1).
Line 24 — not found. The loop terminates with lo > hi; the target was never matched. Return -1.
Complexity → O(log n) time — each iteration halves the search space. O(1) space — only lo, mid, hi pointers.

INTERVIEWFollow-ups they'll ask

  • "What if duplicates are allowed (LC 81)?" When nums[lo] === nums[mid] === nums[hi] you cannot determine which half is sorted, so increment lo and decrement hi — worst case degrades to O(n).
  • "Find the rotation index instead?" LC 153 (Find Minimum in Rotated Sorted Array): the pivot is the first element smaller than its predecessor; use the same sorted-half comparison but track the minimum rather than a target.
  • "Can you recover the pivot first, then binary-search?" Yes — two passes of O(log n) is still O(log n), but the single-pass approach is cleaner and the one interviewers expect.
  • "What breaks if you use strict < instead of ≤ on line 9?" A two-element window where lo === mid would misclassify the left half as unsorted and may loop infinitely or miss the target.

OPTIMAL Binary Search

searchRotated.ts
function search(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length - 1;

  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] === target) return mid;

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

  return -1;
}
Complexity → O(log n) time — each iteration halves the search space. O(1) space — only lo, mid, hi pointers.

ALT 1 Brute force — linear scan

O(n) time · O(1) space

Forget the rotation: walk the array left to right and return the first index where nums[i] === target, or -1 if none.

approach-2.ts
function search(nums: number[], target: number): number {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) return i;
  }
  return -1;
}
Note → Trivially correct and ignores the rotated structure, but it touches every element — O(n). Exploiting the fact that one half is always sorted lets binary search find the target in O(log n).

MNEMONIC The one-liner

"One half is always sorted — find it, range-check target, then commit."

TRIGGERS When you see ___ → reach for ___

"rotated sorted array, O(log n)"sorted-half binary search
identify pivot or minimum in rotated arraynums[lo] ≤ nums[mid] check
standard binary search but array may wraprange-check the sorted half first
LC 81 (with duplicates)same pattern + lo++/hi-- fallback for equals

SKELETON The reusable shape

skeleton.ts
function search(nums: number[], target: number): number {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) {          // left half sorted
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {                               // right half sorted
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

FLASHCARDS Tap to flip

After splitting at mid in a rotated array, which half is always sorted?
At least one. If nums[lo] ≤ nums[mid] the left half is sorted; otherwise the right half is sorted.
tap to flip
1 / 6
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
For nums=[4,5,6,7,0,1,2], target=0, which half is sorted on the first iteration (lo=0, mid=3, hi=6)?
QUESTION 02
What is the time complexity of the rotated binary search?
QUESTION 03
After identifying that the right half is sorted, when do you move hi = mid - 1?
QUESTION 04
Why is nums[lo] ≤ nums[mid] (with =) used instead of strict <?
QUESTION 05
In LC 81 (rotated array with duplicates), what extra case must you handle?
QUESTION 06
nums=[1], target=0. What does the algorithm return?
QUESTION 07
What is the space complexity of this algorithm?
QUESTION 08
#33 · Search in Rotated Sorted ArrayA rotated sorted array always has one sorted half — identify it first, then check whether the target lies within it to halve the search space in O(log n).Which algorithmic approach does this primarily use?
QUESTION 09
#33 · Search in Rotated Sorted ArrayA rotated sorted array always has one sorted half — identify it first, then check whether the target lies within it to halve the search space in O(log n).Which implementation correctly solves it?