Search in a rotated sorted array

The problem, simply

You get an array of different numbers that was sorted, and then rotated: someone cut it at one point and moved the front part to the back. For example [0, 1, 2, 4, 5, 6, 7] can become [4, 5, 6, 7, 0, 1, 2]. You do not know where the cut is.

Given a target, return its index, or -1 if it is not there. Do it in O(log n) time.

A story to remember it

Picture it

Examples

Way 1: the simple way

Look at every number from left to right until you find the target.

class Solution {
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) return i;
        }
        return -1;
    }
}

How long it takes: up to n checks, O(n). Extra room: O(1). It ignores the fact that the array is almost sorted.

Way 2: the clever way

Do binary search, but before choosing a side, find the side that is in order.

1. lo = 0, hi = n - 1. While lo <= hi, take mid.
2. If nums[mid] == target, return mid.
3. If nums[lo] <= nums[mid], the left side lo..mid is in order. If nums[lo] <= target < nums[mid], go left (hi = mid - 1), else go right (lo = mid + 1).
4. Otherwise the right side mid..hi is in order. If nums[mid] < target <= nums[hi], go right, else go left.

Why is one side always in order? The array has only one drop. It is either in the left side or in the right side, never both.

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) return mid;
            if (nums[lo] <= nums[mid]) {                      // left side is in order
                if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else {                                          // right side is in order
                if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }
}

How long it takes: half the range is thrown away each round, O(log n). Extra room: O(1).

Another way: find the cut, then search

First find the index of the smallest number, which is where the cut is. Then do a normal binary search in the sorted part that could hold the target.

To find the cut: if nums[mid] > nums[hi], the drop is to the right of mid, so lo = mid + 1. Otherwise the smallest is at mid or to its left, so hi = mid.

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length, lo = 0, hi = n - 1;
        while (lo < hi) {                       // find the smallest number
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > nums[hi]) lo = mid + 1;
            else hi = mid;
        }
        int cut = lo;
        if (target >= nums[cut] && target <= nums[n - 1]) return find(nums, cut, n - 1, target);
        return find(nums, 0, cut - 1, target);
    }

    private int find(int[] nums, int lo, int hi, int target) {
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }
}

Two binary searches, still O(log n). Some people find this easier to get right under pressure.

Watch out for

• Mixing up the open and closed ends of the ranges. Left: nums[lo] <= target < nums[mid]. Right: nums[mid] < target <= nums[hi]. mid itself was already checked.
• (lo + hi) / 2 can overflow for huge arrays. Use lo + (hi - lo) / 2.
• With repeated numbers, nums[lo] == nums[mid] == nums[hi] hides which side is in order. Then shrink with lo++ and hi--, and the worst case becomes O(n).

What interviewers ask next

• Find the minimum of a rotated array. That is the "find the cut" loop above, comparing nums[mid] with nums[hi].
• How many times was it rotated? The index of the minimum.
• Search when duplicates are allowed (LeetCode 81). Same code, plus the lo++, hi-- step when the ends and middle are equal. Worst case O(n), for example all 1s with a single 2.
• Find a peak element, or search in a bitonic array (goes up then down). Again, binary search on which side is "in order" or rising.

Remember this

Grown-up words: the cut is the rotation point or pivot, the side with no drop is the sorted half, and throwing away half each time is binary search, O(log n).