Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Binary search

Rotated sorted arrays

Lesson · 11 min read · Binary search · Rotated sorted arrays

A rotated array climbs, drops once, and climbs again. Compare with the last element and the drop becomes a first-true search.

The shape

Take a sorted array and move a block from the front to the back: [3, 7, 12, 17, 24, 29, 33, 41] becomes [24, 29, 33, 41, 3, 7, 12, 17]. The result is two sorted runs, and every value in the first run is larger than every value in the second. It is not sorted, so the plain search is wrong, but it still has a test that switches once.

✗024✗129✗233✗341✓43✓57✓612✓717
The test "a[i] ≤ a[n − 1]", here "a[i] ≤ 17": false on the first run, true on the second. The first true is the smallest value, at the rotation point.

Finding the minimum

So the minimum is a lower bound with an unusual test. The values must be distinct for this to hold, and an array that was not rotated at all is the case where the test is true everywhere and the answer is index 0.

The first index whose value is at most the last element, 17.

  1. Step 1 / 5
    0241292333414357612717lohi
    lo0hi8

    We want the first index with a[i] ≤ the last element. The answer is in [lo, hi) = [0, 8); hi = 8 stands for "nothing passes".

  2. Step 2 / 5
    024129233341✓4357612717lomidhi
    lo0mid4hi8

    a[4] = 3: 3 ≤ 17. It passes, so the first pass is at 4 or earlier: hi = 4.

  3. Step 3 / 5
    024129✗233341✓4357612717lomidhi
    lo0mid2hi4

    a[2] = 33: 33 > 17. It fails, and so does everything before it: lo = 3.

  4. Step 4 / 5
    024129✗233✗341✓4357612717lo / midhi
    lo3mid3hi4

    a[3] = 41: 41 > 17. It fails, and so does everything before it: lo = 4.

  5. Step 5 / 5
    024129✗233✗341✓4357612717lo / hi
    answer4

    lo = hi = 4. Index 4 is the first index with a[i] ≤ the last element. The minimum is a[4] = 3, and the array was rotated by 4.

The usual written solution compares a[mid] with a[hi] rather than with the last element. With distinct values the two tests pick out the same boundary; comparing with a[hi] is simply the form most people remember.

Finding a target in one pass

Two ways work. The first finds the rotation point as above and then runs an ordinary search on the run that can hold the target. The second does it in a single loop, using one fact: whichever side of mid the drop is on, the other side is sorted, and for a sorted stretch you can tell at once whether the target lies inside it.

One-pass search in a rotated array

search(a, target)

  1. lo = 0, hi = n − 1. While lo ≤ hi: mid = lo + (hi − lo) / 2. If a[mid] = target, return mid.
  2. If a[lo] ≤ a[mid], the left part a[lo..mid] is sorted: if a[lo] ≤ target < a[mid], hi = mid − 1; otherwise lo = mid + 1.
  3. Otherwise the right part a[mid..hi] is sorted: if a[mid] < target ≤ a[hi], lo = mid + 1; otherwise hi = mid − 1.
  4. Return −1.

Looking for 12. The shaded stretch is the half known to be sorted.

  1. Step 1 / 4
    0241292333414357612717lohi
    target12

    Looking for 12. The array was sorted and then rotated: it climbs, breaks once, and climbs again.

  2. Step 2 / 4
    0241292333414357612717lomidhi
    lo0mid3hi7

    nums[0] = 24 ≤ nums[3] = 41, so the left half is sorted and holds exactly the values from 24 to 41. 12 is not in that range, so it can only be on the right: lo = 4.

  3. Step 3 / 4
    0241292333414357612717lomidhi
    lo4mid5hi7

    nums[4] = 3 ≤ nums[5] = 7, so the left half is sorted and holds exactly the values from 3 to 7. 12 is not in that range, so it can only be on the right: lo = 6.

  4. Step 4 / 4
    0241292333414357612717lo / midhi
    lo6mid6hi7

    nums[6] = 12. Return 6.

Repeated values break the guarantee

With duplicates, a[lo] = a[mid] = a[hi] says nothing about where the drop is: in [1, 1, 1, 1, 0, 1, 1] and [1, 1, 0, 1, 1, 1, 1] the three probes see the same values. The only safe move is to discard one copy from each end and try again, which in the worst case visits every element.

TimeO(log n) with distinct values; O(n) worst case with repeats
SpaceO(1)

The O(n) is not a weakness of the method. An array of equal values with one different value hidden somewhere forces any algorithm to look at every position.

Problems in this module