Binary search on a rotated array

How does Binary search on a rotated array work?

A rotated array is one sorted run, cut and swapped. Each of the two pieces is still sorted.

Take the middle index as usual. Compare the value there with the value at the low bound.

If the low value is not larger, the left half is the sorted one. Otherwise the right half is.

Now one half is fully understood. Its two ends bracket every value inside it.

Check whether the target falls between those ends. If it does, search that half, otherwise search the other.

Either way half of the range disappears. The cost stays log n.

1. lo=0 hi=6, mid=3, value 7Searching [4, 5, 6, 7, 0, 1, 2] for a 0.
2. left half 4 to 7 is sortedThe low value is 4 and mid is 7. So the left side never wraps.
3. lo=4 hi=60 does not fall between 4 and 7. The answer must be on the right.
4. mid=5, value 1, left half 0 to 1The left half is sorted again. This time 0 falls inside it.
5. lo=4 hi=4, value 0One candidate is left and it matches. Three steps for seven elements.

function searchRotated(arr, target) {
    let lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        if (arr[mid] === target) return mid;
        if (arr[lo] <= arr[mid]) {
            if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

A worked example of Binary search on a rotated array

Smallest value in a rotated array

A sorted array was rotated an unknown number of times. Find its smallest value.

The values are all distinct, and scanning the whole array is not allowed.

Compare the middle value against the value at the high bound.

If mid is larger, the rotation point lies to its right. Otherwise the minimum is mid or left of it.

function findMin(nums) {
    let lo = 0;
    let hi = nums.length - 1;

    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);

        // compare against the right end, never the left
        if (nums[mid] > nums[hi]) {
            lo = mid + 1; // the rotation point is further right
        } else {
            hi = mid;     // mid may itself be the minimum
        }
    }

    return nums[lo];
}

When should you use Binary search on a rotated array?

These phrases in a problem statement point here:

• •sorted array rotated at an unknown pivot
• •find a target in O(log n)
• •no duplicates (or handle them separately)
• •find the minimum / the rotation point
• •array increases then drops once

What is Binary search on a rotated array confused with?

• Binary search (array): A plain search compares the middle against the target. Here it is compared against a bound first.
• Linear search: A scan handles a rotated array with no reasoning at all. It costs O(n) instead of O(log n).
• Binary search on the answer: There the range is made of candidate answers. Here you are searching real stored values.
• Fast sort (merge / quick): Sorting restores the order but costs n log n. The rotation already leaves enough order to use.

Common mistakes with Binary search on a rotated array

• Comparing the middle with the target first

  The target says nothing about which half is sorted. Compare the middle against a bound instead.

• Moving high past mid while hunting a minimum

  The middle element may be the minimum itself. Only the low bound may skip over it.

• Assuming a rotation actually happened

  A rotation of zero is still valid input. The sorted-half test has to cover that case.

• Ignoring duplicate values

  When both bounds hold the same value, neither half can be identified. The only safe move shrinks by one.

Which interview problems use Binary search on a rotated array?

• Search in rotated sorted array: The plain form, with distinct values.
• Search in rotated sorted array II: Duplicates force a linear worst case.
• Find minimum in rotated sorted array: Compare against the high bound instead of the target.
• Find minimum in rotated sorted array II: The same, with the duplicate case handled by hand.
• Find how far the array was rotated: The index of the minimum is the rotation count.
• Peak index in a mountain array: The same halving, driven by a neighbour comparison.
• Find in mountain array: Locate the peak first, then search each side.

What is the time and space complexity of Binary search on a rotated array?

O(log n)

n up to 1e9 gives O(log n), the same as a plain search. Duplicates push the worst case to O(n).