Skip to content
16-Week DSA Roadmap
LeetCode #33MediumProblem 1 of 8

Search in Rotated Sorted Array

A sorted array was turned like a dial. Find a target's index in O(log n) by working out which half is still sorted.

  • Binary search on a rotated array
  • Find the sorted half

Before this, know: Classic binary search (week 3), Arrays and indexes

The problem in plain English

Start with a sorted array: the numbers go up from left to right, like [0, 1, 2, 4, 5, 6, 7]. Now rotate it: take some numbers off the front and stick them on the back, keeping their order. Moving [0, 1, 2] to the back gives [4, 5, 6, 7, 0, 1, 2].

You get the rotated array nums and a number target. Return the index (position, counting from 0) of target, or -1 if it isn’t there.

nums
  1. 40
  2. 51
  3. 62
  4. 73
  5. 04
  6. 15
  7. 26
nums = [4, 5, 6, 7, 0, 1, 2], target = 0. The 0 sits at index 4, so the answer is 4.

The rules that matter:

  • All the numbers are different (no duplicates).
  • You don’t know how far it was rotated. It might not be rotated at all.
  • The problem asks for O(log n) time. That phrase is a loud hint: it means “use binary search”. (O(log n) means: double the array, and the work grows by just one extra step.)

Before you code: think it through

Draw the array as bars and you see two rising ramps with one drop between them:

40516273041526the drop
A rotated sorted array is two sorted runs. The only place a number is followed by a smaller one is the drop, between 7 and 0.

Here’s the fact the whole solution rests on. Pick any middle index. The drop is on one side of it, so the other side has no drop: it is sorted. And with a sorted stretch, we know exactly which numbers it can contain: everything between its first and last value.

40516273041526the dropmid
With mid at index 3 (value 7): nums[0] = 4 ≤ 7, so the left part 4, 5, 6, 7 has no drop. It is sorted (shaded).

Pause and think

nums = [6, 7, 1, 2, 3, 4, 5], and mid is index 3 (value 2). Which half is sorted? Could the target 7 be in it?

Approach 1: Brute force

Forget about the sorting and look at every number from left to right until we find the target. We use one pointer i (a variable that holds a position).

Brute force: check every number

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

nums
  1. 40
  2. 51
  3. 62
  4. 73
  5. 04
  6. 15
  7. 26
variables
target
0
checks
1
answer
—
  • Checking now
  • Already checked
  • Target

Check #1: nums[0] = 4, not 0. Move on.

Step 1 / 6

Which line is running?

function search(nums, target) {  for (let i = 0; i < nums.length; i++) {Running now:     if (nums[i] === target) {      return i;    }  }  return -1; // looked everywhere: not there}

Brute force: linear scan

function search(nums, target) {  for (let i = 0; i < nums.length; i++) {    if (nums[i] === target) {      return i;    }  }  return -1; // looked everywhere: not there}
def search(nums, target):    for i in range(len(nums)):        if nums[i] == target:            return i    return -1  # looked everywhere: not there

Why is it slow?

It’s correct, but it can look at every element. For 7 numbers that’s up to 7 checks. For 5,000 numbers (LeetCode’s limit) it’s up to 5,000 checks. That is O(n): double the array, double the work. It completely ignores the fact that the array is (almost) sorted.

Binary search would need only about 13 checks for 5,000 numbers, because each check throws away half of what’s left (5,000 → 2,500 → 1,250 → … → 1).

The pattern: binary search on a rotated array

You learned plain binary search in week 3: keep a range lo..hi, look at the middle, and throw away the half that can’t contain the target. The only new problem here is “how do I know which half to throw away when the array isn’t fully sorted?”

Pattern

Binary search on a rotated array

Template

Use it when: the array was sorted and then rotated (shifted around in a circle), and you need O(log n).

Signal words

  • “rotated sorted array”
  • “sorted then rotated”
  • “pivot”
  • “O(log n)”
  • “distinct values”

Approach 2: Binary search on the sorted half

  1. Set lo = 0 and hi = n − 1. The target, if it exists, is somewhere in lo..hi.
  2. While lo <= hi, compute mid = (lo + hi) // 2 (rounded down).
  3. If nums[mid] is the target, return mid.
  4. If nums[lo] <= nums[mid], the left half lo..mid is sorted. If nums[lo] <= target < nums[mid], the target is in it: hi = mid − 1. Otherwise lo = mid + 1.
  5. Else the right half mid..hi is sorted. If nums[mid] < target <= nums[hi], the target is in it: lo = mid + 1. Otherwise hi = mid − 1.
  6. If the loop ends (lo > hi), the target isn’t there: return −1.

Press Play and watch the shaded window: it marks the half we just proved is sorted. Faded cells are thrown away for good. Try “Right half sorted” to see the other branch, and the edge cases.

Binary search: find the sorted half

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

nums
  1. 40
  2. 51
  3. 62
  4. 73
  5. 04
  6. 15
  7. 26
variables
target
0
lo
0
hi
6
mid
—
sorted half
—
answer
—
  • The half we proved is sorted
  • nums[mid]
  • Thrown away
  • Target

We look for 0. The search range is everything: lo = 0 and hi = 6. The array was sorted, then rotated, so somewhere there may be a "drop" where a big number is followed by a small one.

Step 1 / 11

Which line is running?

function search(nums, target) {Running now:   let lo = 0;  let 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 [lo..mid] is sorted.      if (nums[lo] <= target && target < nums[mid]) {        hi = mid - 1; // target is inside the sorted left half      } else {        lo = mid + 1; // target must be on the right      }    } else {      // Right half [mid..hi] is sorted.      if (nums[mid] < target && target <= nums[hi]) {        lo = mid + 1; // target is inside the sorted right half      } else {        hi = mid - 1; // target must be on the left      }    }  }  return -1; // the range is empty: target is not in nums}

Notice that each step costs only a couple of comparisons, and half of the range disappears every time.

The code, line by line

Binary search on the sorted half

function search(nums, target) {  let lo = 0;  let 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 [lo..mid] is sorted.      if (nums[lo] <= target && target < nums[mid]) {        hi = mid - 1; // target is inside the sorted left half      } else {        lo = mid + 1; // target must be on the right      }    } else {      // Right half [mid..hi] is sorted.      if (nums[mid] < target && target <= nums[hi]) {        lo = mid + 1; // target is inside the sorted right half      } else {        hi = mid - 1; // target must be on the left      }    }  }  return -1; // the range is empty: target is not in nums}
def search(nums, target):    lo, hi = 0, len(nums) - 1    while lo <= hi:        mid = (lo + hi) // 2        if nums[mid] == target:            return mid        if nums[lo] <= nums[mid]:            # Left half [lo..mid] is sorted.            if nums[lo] <= target < nums[mid]:                hi = mid - 1  # target is inside the sorted left half            else:                lo = mid + 1  # target must be on the right        else:            # Right half [mid..hi] is sorted.            if nums[mid] < target <= nums[hi]:                lo = mid + 1  # target is inside the sorted right half            else:                hi = mid - 1  # target must be on the left    return -1  # the range is empty: target is not in nums

The two versions drift by a line here and there (JavaScript sets lo and hi on two lines, Python returns mid on its own line), so below “JS n / Py m” gives both line numbers. On LeetCode the Python version lives inside class Solution as def search(self, nums, target); the body is the same.

  • JS 2–3 / Py 2: the search range starts as the whole array. hi is the last index, n − 1.
  • JS 4 / Py 3: keep going while the range lo..hi still has at least one number.
  • JS 5 / Py 4: the middle index. Math.floor in JS and // in Python round down, so mid is always a whole number.
  • JS 6 / Py 5–6: lucky hit, we’re done.
  • JS 7 / Py 7: the key test. If the first number of the range is ≤ the middle one, nothing drops between them, so lo..mid is sorted. We use <= (not <) because when lo === mid the “half” is a single number, which counts as sorted.
  • JS 9 / Py 9: is the target inside the sorted left half? It must be at least nums[lo] and less than nums[mid] (we already know it isn’t equal to nums[mid]). Python can chain the comparison: nums[lo] <= target < nums[mid].
  • JS 10 & 12 / Py 10 & 12: shrink the range to the half that can still hold the target.
  • JS 16–19 / Py 15–18: the mirror image when the right half mid..hi is the sorted one: the target must be greater than nums[mid] and at most nums[hi].
  • JS 23 / Py 19: the range became empty, so the target isn’t in the array.

Dry run

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

lohimidnums[mid]sorted halftarget in it?next range
0637left: 4..7no (0 < 4)lo = 4
4651left: 0..1yes (0 ≤ 0 < 1)hi = 4
4440—found!return 4
nums = [4, 5, 6, 7, 0, 1, 2], target = 0

The first row (mid = 3, where nums[mid] is 7) is the interesting one: 0 is smaller than everything, so a beginner might search left. But the left half is the sorted run 4..7, which can’t hold a 0, so we correctly go right, past the drop.

Complexity

Brute force

Time

O(n)

Might look at every number once: 5,000 numbers, up to 5,000 checks.

Space

O(1)

Just the index i.

Binary search on the sorted half

Time

O(log n)

Every loop throws away half the range. 5,000 numbers need at most about 13 loops.

Space

O(1)

Only three numbers: lo, mid and hi.

Common mistakes and edge cases

What to say out loud:

  1. “O(log n) means binary search, but the array isn’t fully sorted, so I need a new rule for which half to drop.”
  2. “Any mid splits the range in two, and the single drop is in only one of them, so the other half is sorted.”
  3. “I can check whether the target lies in the sorted half just by comparing with its two ends.”
  4. “Each step halves the range: O(log n) time, O(1) space.”
  5. Dry-run a case where the target is on the far side of the drop (like 0 above).

Likely follow-ups:

  • “Find the minimum of a rotated array.” That’s Find Minimum in Rotated Sorted Array (LeetCode 153) from week 3. Same idea: compare nums[mid] with nums[hi] to see which side the drop (and the minimum) is on.
  • “What if there are duplicates?” (LeetCode 81) Then nums[lo] == nums[mid] doesn’t tell you which half is sorted; you shrink by one (lo++), and the worst case becomes O(n).

Related problems: