Topics › Binary Search › BS on 1D Arrays

Search in rotated sorted array-I

Medium TUF ID 87 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

An array of distinct integers was sorted in ascending order and then rotated at some unknown index k: the array [a0, a1, ..., a(n-1)] became [ak, ak+1, ..., a(n-1), a0, ..., ak-1]. Rotating by 0 is allowed, so the array may still be fully sorted. Given such an array nums and a target, return the index of target, or -1 if it is not present, in O(log n) time.

Constraints: 0 ≤ n ≤ 10^4, all values distinct, values and target fit in a 32-bit signed integer.

Example 1

nums = [4, 5, 6, 7, 0, 1, 2], target = 0
answer = 4                // the sorted array [0..7] was rotated 4 places

Example 2

nums = [4, 5, 6, 7, 0, 1, 2], target = 3
answer = -1               // 3 falls in the gap between the two sorted runs

Example 3

nums = [1], target = 0
answer = -1

Approach 1: Brute force, linear scan

Intuition. Ignore the structure and look everywhere. This is the only approach that does not depend on the array being a rotation of a sorted array, which makes it the right oracle for testing the clever ones.

Algorithm.

1. For i from 0 to n - 1: if nums[i] == target, return i.
2. Return -1.

static int bruteForce(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) return i;
    }
    return -1;
}

Complexity. Time O(n), space O(1).

Approach 2: Better, find the rotation point, then binary search one run

Intuition. A rotated sorted array is two sorted runs glued together: nums[0..pivot-1] (the larger values) followed by nums[pivot..n-1] (the smaller values), where pivot is the index of the minimum. If we knew pivot, we could decide in O(1) which run can contain target by comparing it with the run’s smallest and largest values, and then do a plain binary search inside that run.

Finding pivot is itself a binary search. Compare nums[mid] with nums[hi]. If nums[mid] > nums[hi], the “drop” from large values to small ones lies strictly to the right of mid, so the minimum is in [mid + 1, hi]. Otherwise nums[mid] < nums[hi] (values are distinct), so [mid, hi] is sorted and the minimum is at mid or to its left: hi = mid. When lo == hi we have the pivot.

Algorithm.

1. If n == 0, return -1.
2. Binary search for pivot: lo = 0, hi = n - 1; while lo < hi, mid = lo + (hi - lo) / 2; if nums[mid] > nums[hi], lo = mid + 1, else hi = mid. Then pivot = lo.
3. If nums[pivot] <= target <= nums[n - 1], search [pivot, n - 1]; otherwise search [0, pivot - 1].
4. Ordinary binary search on the chosen range; return the index or -1.

static int better(int[] nums, int target) {
    int n = nums.length;
    if (n == 0) return -1;
    // step 1: index of the smallest element (the rotation point)
    int lo = 0, hi = n - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) lo = mid + 1;   // the drop is to the right of mid
        else hi = mid;                            // nums[mid] < nums[hi]: minimum is mid or left of it
    }
    int pivot = lo;
    // step 2: choose the sorted segment whose value range contains target
    if (target >= nums[pivot] && target <= nums[n - 1]) {
        lo = pivot; hi = n - 1;
    } else {
        lo = 0; hi = pivot - 1;
    }
    // step 3: ordinary binary search inside [lo, hi]
    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;
}

Complexity. Time O(log n): two binary searches. Space O(1).

When the array is not rotated, pivot = 0. Then either target is within [nums[0], nums[n - 1]] and we search the whole array, or it is outside and the left range [0, -1] is empty, returning -1 immediately. Both are correct.

Approach 3: Optimal, one binary search using the sorted half

Intuition. We can skip finding the pivot. Take any range [lo, hi] of a rotated sorted array and its midpoint mid. At least one of the halves [lo, mid] and [mid, hi] is sorted, because the single “drop” can only be in one of them. And we can tell which: if nums[lo] <= nums[mid], the left half is sorted; otherwise the right half is.

A sorted half is something we understand completely: target is inside it exactly when it lies between its first and last values. So at every step we check whether target fits in the sorted half’s value range. If yes, continue in that half. If no, target can only be in the other half, so continue there, even though we do not know what that half looks like. Either way the range halves.

Algorithm.

1. lo = 0, hi = n - 1.
2. While lo <= hi:
   • mid = lo + (hi - lo) / 2. If nums[mid] == target, return mid.
   • If nums[lo] <= nums[mid] (left half sorted): if nums[lo] <= target < nums[mid], hi = mid - 1; else lo = mid + 1.
   • Else (right half sorted): if nums[mid] < target <= nums[hi], lo = mid + 1; else hi = mid - 1.
3. Return -1.

static int optimal(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 half [lo, mid] is sorted
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;   // target fits in the left half
            else lo = mid + 1;                                        // otherwise it must be on the right
        } else {                                                      // right half [mid, hi] is sorted
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;   // target fits in the right half
            else hi = mid - 1;                                        // otherwise it must be on the left
        }
    }
    return -1;
}

Dry run on nums = [4, 5, 6, 7, 0, 1, 2], target = 0:

And for target = 3: the first step is identical (lo = 4); at mid = 5 the left half [0, 1] does not contain 3, so lo = 6; at mid = 6, nums[6] = 2, the left half [2, 2] does not contain 3, so lo = 7 > hi and we return -1.

Complexity. Time O(log n): one comparison round per halving. Space O(1).

Why is nums[lo] <= nums[mid] enough to conclude the left half is sorted? If the drop were inside [lo, mid], then nums[mid] would belong to the smaller run and nums[lo] to the larger run, which forces nums[mid] < nums[lo]. The <= (rather than <) covers the case lo == mid, where the half is a single element and trivially sorted. With distinct values this reasoning is airtight; with duplicates it breaks, which is exactly what the follow-up problem is about.

Edge cases and pitfalls

• Not rotated. pivot = 0; the optimal method always finds the left half sorted and degenerates into ordinary binary search.
• Rotated by n - 1. The minimum is the last element, for example [2, 3, 4, 5, 1]. Tested in the Java file along with “rotated once”.
• One or two elements. [1] and [3, 1] exercise the lo == mid case where the “left half” is a single element.
• Empty array. Return -1; the better method checks n == 0 before reading nums[pivot].
• Target in the gap. Values between the maximum of the smaller run and the minimum of the larger run (3 in Example 2) are absent even though they lie within [min, max] of the array.
• Using <= versus < in the range tests. nums[lo] <= target < nums[mid] and nums[mid] < target <= nums[hi] deliberately exclude nums[mid], which has already been compared. Including it is harmless; excluding it is tidy.
• Duplicates. The sorted-half test can fail when nums[lo] == nums[mid] == nums[hi]. This problem forbids duplicates; the sequel handles them.
• Overflow in mid. Use lo + (hi - lo) / 2.

Related problems

• Search in rotated sorted array-II allows duplicates and shows how the sorted-half test must be patched.
• Find minimum in Rotated Sorted Array is step 1 of the better approach as a problem of its own.
• Find out how many times the array is rotated returns the pivot index itself.
• Search X in sorted array is the unrotated version.