Search in Rotated Sorted Array

The problem

An array of n different numbers was sorted from small to large and then rotated: a block from the front was moved, in order, to the back. So [1, 3, 5, 7, 9] might become [7, 9, 1, 3, 5].

You get the rotated array nums and a number target. Return the index of target in nums, or −1 if it is not there. Your code must run in O(log n) time, where n is the length of nums.

Example 1

Input: nums = [14, 16, 18, 1, 3, 5, 7, 9, 11], target = 9

Output: 7

9 sits at index 7.

nums

1401611821334557697118

target

9

Example 2

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

Output: -1

5 is not in the array.

Example 3

Input: nums = [8], target = 8

Output: 0

One number, and it is the target.

Constraints

• 1 ≤ n ≤ 5,000
• −10,000 ≤ nums[i], target ≤ 10,000
• All numbers are different.
• nums is a sorted array that may have been rotated.

Clarifying questions

Can numbers repeat?

No. With repeats, nums[low] can equal nums[middle] and we could not tell which half is sorted.

Do we know how far it was rotated?

No. Finding the rotation point first is one way, but it is not needed.

What if the target is missing?

Return −1.

Can the array be not rotated at all?

Yes. Then it is plain sorted, and the same code still works.

Spot the pattern

The array is two sorted runs, and the problem asks for O(log n). That means binary search: halve the range at every step. Plain binary search needs the whole range sorted. The key fact here is weaker but enough: cut a rotated array anywhere, and at least one of the two halves is sorted.

Solutions

Linear scanO(n)Binary searchO(log n)

Show all

Finding the rotation point first and then running a normal binary search also takes O(log n). It is two searches instead of one, so it is not a real middle step.

Linear scan O(n)

The idea

Check every index from left to right and return the first one that holds the target. If none does, return −1. It is always correct, but it does not use the order at all.

Walkthrough

nums

1401611821334557697118

target

9

1. for i in range(len(nums)):
2. if nums[i] == target:
3. return i
4. return -1

Check each index from the left. Stop at the first number equal to 9.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Linear scan: check every index until we find the target.
    // Always correct, but it ignores the order, so O(n) time.
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) return i;
        }
        // We looked at every number, so the target is not there.
        return -1;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit line compares one number with the target. It sits inside one loop, and one comparison is 1 step.

   1. for i in range(len(nums)):
   2. if nums[i] == target:
   3. return i
   4. return -1

2. 2 Count the runs on Example 1

   Example 1 has 9 numbers. The target sits at index 7, so the loop checks indexes 0 to 7.

   8 runs.

   i	0	1	2	3	4	5	6	7
   nums[i]	14	16	18	1	3	5	7	9

3. 3 Write the count for any n

   The worst case is a target that is missing. Then the loop checks every index:

   n times

   Check it with Example 1: a missing target would take 9 runs. The real 8 is one less, because 9 is near the end.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. The count is already n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The code keeps only i. The space is O(1).

   i

Binary search O(log n)

The idea

Keep a range low..high that must hold the target if it exists. Look at the middle position, middle. If it is the target, done. If not, find the sorted half:

• If nums[low] ≤ nums[middle], the left half low..middle has no drop, so it is sorted.
• Otherwise the drop is on the left, so the right half middle..high is sorted.

A sorted half has a known smallest and largest number, at its two ends. So one check tells us if the target is inside it. If yes, keep that half. If no, keep the other half. Either way, half the range is gone.

Why it never misses the answer: we only drop a half after proving the target cannot be in it. For the sorted half, its two ends prove it. For the other half, we only drop it when the target is inside the sorted one.

Walkthrough

nums

1401611821334557697118

lowhigh

target

9

1. low, high = 0, len(nums) - 1
2. while low <= high:
3. middle = (low + high) // 2
4. if nums[middle] == target: return middle
5. if nums[low] <= nums[middle]: # left half sorted
6. if nums[low] <= target < nums[middle]: high = middle - 1
7. else: low = middle + 1
8. else: # right half sorted
9. if nums[middle] < target <= nums[high]: low = middle + 1
10. else: high = middle - 1
11. return -1

If 9 is in the array, it is inside low..high. At the start that is the whole array.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Binary search: one half of low..high is always sorted, and its two ends tell us
    // whether the target can be inside it. Each step halves the range: O(log n).
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int middle = low + (high - low) / 2;
            if (nums[middle] == target) return middle;
            // <= and not <: when low == middle, the left half is one number, which is sorted.
            if (nums[low] <= nums[middle]) {
                // Left half is sorted, so its ends bound every number in it.
                if (nums[low] <= target && target < nums[middle]) high = middle - 1;
                else low = middle + 1;
            } else {
                // The drop is on the left, so the right half is sorted.
                if (nums[middle] < target && target <= nums[high]) low = middle + 1;
                else high = middle - 1;
            }
        }
        // The range is empty, so the target is not there.
        return -1;
    }
}

Big O

Time O(log n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each run of the loop finds the middle, compares a few numbers and moves one end. That is the same small job every time, so each run is 1 step. There is one loop.

   1. low, high = 0, len(nums) - 1
   2. while low <= high:
   3. middle = (low + high) // 2
   4. if nums[middle] == target: return middle
   5. if nums[low] <= nums[middle]: # left half sorted
   6. if nums[low] <= target < nums[middle]: high = middle - 1
   7. else: low = middle + 1
   8. else: # right half sorted
   9. if nums[middle] < target <= nums[high]: low = middle + 1
   10. else: high = middle - 1
   11. return -1

2. 2 Count the runs on Example 1

   Example 1 has 9 numbers. The table shows how many numbers are in low..high at the start of each run: 9, then 4, then 2. The third run finds 9.

   3 runs.

   	run 1	run 2	run 3
   numbers left	9	4	2

3. 3 Write the count for any n

   Each run drops middle and one half, so the range at least halves. After k runs, at most n / 2ᵏ numbers are left. In the worst case the loop runs until the range is empty:

   at most ⌊log₂ n⌋ + 1 runs

   Check it with Example 1: log₂ 9 is about 3.2, so at most 4 runs. It took 3, because the target was found before the range ran out.

4. 4 Keep only the part that grows fastest

   Drop the + 1. One extra run does not change how the work grows. What is left is log n. Doubling n adds just one run.

   So the time is O(log n).

5. S Space: count the extra memory the same way

   The code keeps low, high and middle. That is 3 variables, whatever n is, so the space is O(1).

   lowhighmiddle

Common mistake

Using < instead of ≤ for the sorted test

When low equals middle (a range of one or two numbers), nums[low] < nums[middle] is false, so the code wrongly treats the right half as sorted. With [3, 1] and target 1, it then drops the 1. Use nums[low] <= nums[middle].

Tested at the limits

2,000 random rotated arrays of 1 to 8 different numbers, rotated by any amount, with a target that is often missing. Then every one of the 5,000 rotations of the largest array, each with one present and one missing target. The linear scan and the binary search gave the same answer every time.

Largest inputs	Result
5,000 numbers (the most allowed), rotated, with a target that falls in a gap, so the search runs until the range is empty. Binary search.	Under 0.001 s, and under 0.001 MB of extra memory: just three indexes (low, middle and high).