Start learning free

LESSON 383 OF 673 · BINARY SEARCH

Search in Rotated Sorted Array in Python: O(log n) Binary Search

Practice O(log n) Read the full explanation

You get an integer target and a list nums of different integers.

Return the index of target in nums, or -1 if nums doesn't have it.

The numbers in nums were sorted from smallest to largest. Then the array may have been rotated. A rotation moves the first k numbers to the end, in the same order. Here 0 <= k < len(nums).

For example, [2,5,8,10,13] with k = 2 becomes [8,10,13,2,5]. With k = 0, nothing moves.

 

Example 1:

Input: nums = [15,18,22,3,7,11], target = 7
Output: 4
Explanation: The sorted array was rotated with k = 3.
So 3, 7 and 11 moved to the end.
7 is at index 4.

Example 2:

Input: nums = [9,12,2,5], target = 6
Output: -1
Explanation: 6 is not in the array.

Example 3:

Input: nums = [8], target = 8
Output: 0

 

Constraints:

  • 1 to 1,000,000 numbers.
  • All numbers are different.
  • target and each number are from -109 to 109.
  • The array is sorted, then maybe rotated (see above).

Note:

Your algorithm should run in O(log n) time and use O(1) extra space.

STEP 1 OF 11
    Ctrl + Enter to check

    PYTHON · BINARY SEARCH

    Search In Rotated Sorted Array in Python, explained

    Problem overview

    The method search receives a list of distinct integers, nums, and a number target. The list was sorted in ascending order and then possibly rotated: its first k elements were moved, in the same order, to the end. For example, [0, 1, 2, 4, 5, 6, 7] rotated at k = 3 becomes [4, 5, 6, 7, 0, 1, 2]. The method returns the index of target in the rotated list, or -1 if it is not there.

    With nums = [4, 5, 6, 7, 0, 1, 2], the target 0 is at index 4, and the target 3 is missing, so the answer is -1. The lesson asks for O(log n) time and O(1) extra space, which rules out a plain scan with O(n) time and points to binary search.

    Approach: find the sorted half, then decide

    Ordinary binary search needs the whole list to be sorted. A rotated list is not, since it rises, drops once at the rotation point, and rises again. But it still has a useful property: wherever the rotation point is, at least one of the two halves around middle is sorted. The values drop only once, so the drop falls in at most one half, and the other half rises from end to end.

    In a sorted range, two comparisons with its ends tell whether a value can be inside it. So each pass of the loop does this:

    1. Check nums[middle]. If it equals target, return middle.
    2. Find which half is sorted: the left half is sorted when nums[left] <= nums[middle]. Otherwise the right half is.
    3. If target lies between the ends of the sorted half, keep that half. If not, it can only be in the other half, so keep that one.

    Each pass discards half of the window, so the loop runs about log2 n times.

    The search for 0 in [4, 5, 6, 7, 0, 1, 2] goes like this. At first left is 0, right is 6 and middle is 3, which holds 7. The left half, 4 to 7, is sorted, and 0 is not in it, so the search moves right. Next the window is indexes 4 to 6 and middle is 5, which holds 1. The left half of this window, the elements 0 and 1, is sorted, and 0 lies in it, so right moves to 4. Finally middle is 4, which holds 0, and the method returns 4. For the target 3, the same steps end with an empty window, and the answer is -1.

    Step by step

    1. Set the window: left, right = 0, len(nums) - 1. Both ends are inclusive, so the window is every index from left to right.
    2. Loop while left <= right. When the two are equal, one element is still left to check, which is why the comparison is <=.
    3. Compute middle as left + (right - left) // 2, using floor division so it stays a whole number.
    4. Return middle on a match. This check comes first, so the steps below only decide which half to drop.
    5. Test whether the left half is sorted: nums[left] <= nums[middle]. The <= covers the case where left equals middle: one element counts as sorted.
    6. In a sorted left half, if nums[left] <= target and target < nums[middle], drop the right half by moving right to middle - 1. The upper comparison is strict because nums[middle] was already checked.
    7. Otherwise the target can't be in the sorted left half, so move left to middle + 1.
    8. In the other case, the right half is sorted. If nums[middle] < target and target <= nums[right], drop the left half by moving left to middle + 1.
    9. Otherwise the target can only be in the left half, so move right to middle - 1.
    10. After the loop the window is empty, which means every index that could hold the target was ruled out. Return -1.

    The solution in Python

    class Solution:
        def search(self, nums: List[int], target: int) -> int:
            left, right = 0, len(nums) - 1
            while left <= right:
                middle = left + (right - left) // 2
                if nums[middle] == target:
                    return middle
                if nums[left] <= nums[middle]:
                    if nums[left] <= target and target < nums[middle]:
                        right = middle - 1
                    else:
                        left = middle + 1
                else:
                    if nums[middle] < target and target <= nums[right]:
                        left = middle + 1
                    else:
                        right = middle - 1
            return -1
    

    The Python details that matter here:

    • // is floor division. It returns an integer, where / would return a float, and a float can't be used as a list index.
    • left + (right - left) // 2 gives the same index as (left + right) // 2. Python integers never overflow, so either form is safe here. The first form is the habit that carries over to languages with fixed-size integers.
    • Tuple assignment in left, right = 0, len(nums) - 1 sets both variables in one line.
    • Chained comparisons are available. nums[left] <= target < nums[middle] would mean the same as the two comparisons joined with and. The lesson's version spells them out.
    • Negative indices. A negative index counts from the end in Python, so nums[-1] does not raise an error. The window arithmetic keeps middle between left and right, so the loop never indexes outside it.

    Complexity

    Time: O(log n). Each pass of the loop either returns or discards at least half of the window, so there are at most about log2 n passes, and each does constant work.

    Space: O(1). The method keeps three integers, left, right and middle, and never copies the list.

    Edge cases and common mistakes

    • A list that was not rotated. With k = 0 the list is plain sorted, the left half is always sorted, and the method behaves as ordinary binary search. [1, 2, 3, 4] with target 3 gives 2.
    • One element. [1] with target 1 gives 0, and with target 0 gives -1.
    • Two elements. [3, 1] with target 1 gives 1. Here middle equals left, so the left half is one element. With a strict nums[left] < nums[middle] as the test, that element would not count as sorted and the method would return -1.
    • The target is the first element. [5, 1, 3] with target 5 gives 0.
    • The target is missing. The window shrinks to empty and the method reaches the final return -1.
    • Testing the wrong half. Compare the target with the ends of the half that is sorted. The other half has the drop in it, and comparing with its ends proves nothing.
    • Distinct values. The test nums[left] <= nums[middle] relies on the values being distinct. With repeats, it can't always tell which half is sorted.

    Testing

    • nums = [4, 5, 6, 7, 0, 1, 2], target = 0 gives 4.
    • nums = [4, 5, 6, 7, 0, 1, 2], target = 3 gives -1.
    • nums = [6, 7, 1, 2, 3, 4, 5], target = 7 gives 1.
    • nums = [3, 1], target = 1 gives 1.
    • nums = [1], target = 0 gives -1.
    Keep going with Python650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free