☕ DSA Java Articles

Topics › Binary Search › BS on 1D Arrays

Search element in a sorted and rotated array/ find pivot where it is rotated

Medium TUF ID 2769 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A sorted array of distinct integers has been rotated to the right by an unknown amount r (0 ≤ r < n): its last r elements were moved, in order, to the front. For example [0, 1, 2, 4, 5, 6, 7] rotated by r = 4 becomes [4, 5, 6, 7, 0, 1, 2]. Given the rotated array nums and a target, return the index of target, or -1 if it is absent. The intended solution runs in O(log n).

The title also asks for the pivot: the index where the rotation happened. That is the index of the smallest element, and it equals the rotation amount r. Approach 2 computes it explicitly.

Constraints: 0 ≤ n ≤ 5000, all values distinct, values fit in an int.

Example 1

nums = [4, 5, 6, 7, 0, 1, 2], target = 0
answer = 4          // pivot is index 4 (value 0), and target sits there

Example 2

nums = [4, 5, 6, 7, 0, 1, 2], target = 3
answer = -1         // 3 is not in the array

Approach 1: Brute force, linear scan

Intuition. Ignore the structure and compare every element with the target. Correct for any array, rotated or not, but it throws away the ordering that makes O(log n) possible.

Algorithm.

  1. For each index i, 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 pivot, then binary search one part

Intuition. A rotated sorted array is two sorted runs glued together: nums[0..p-1] and nums[p..n-1], where p is the pivot (the index of the minimum). Every value in the left run is larger than every value in the right run. If we knew p, we could tell from the target’s value which run it must be in, then run an ordinary binary search on that run.

To find p, compare nums[mid] with the last element of the current range, nums[hi]:

Comparing with nums[hi] rather than nums[lo] matters. If the range is not rotated at all, nums[lo] ≤ nums[mid] is true, and a rule like “left half sorted, go right” would skip the minimum at lo. The comparison with hi has no such blind spot.

Algorithm.

  1. Find p with the loop above: lo = 0, hi = n - 1; while lo < hi, move lo = mid + 1 or hi = mid. When they meet, lo is the pivot.
  2. The right run nums[p..n-1] holds exactly the values from nums[p] (the minimum) to nums[n-1]. If target is in that range, binary search it there.
  3. Otherwise binary search the left run nums[0..p-1]. When the array is not rotated, p = 0 and this run is empty.
static int findPivot(int[] nums) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) lo = mid + 1;        // the drop is somewhere right of mid
        else hi = mid;                                 // mid..hi is sorted: minimum is at mid or left of it
    }
    return lo;
}

static int binarySearch(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;
}

static int better(int[] nums, int target) {
    int n = nums.length;
    if (n == 0) return -1;
    int p = findPivot(nums);
    if (target >= nums[p] && target <= nums[n - 1]) return binarySearch(nums, p, n - 1, target);
    return binarySearch(nums, 0, p - 1, target);
}

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

Intuition. We can skip the separate pivot search. Pick any mid in a rotated range lo..hi. The single “drop” in the array can be in at most one of the halves lo..mid and mid..hi, so at least one half is fully sorted. We can tell which by comparing endpoints: if nums[lo] ≤ nums[mid], the left half has no drop; otherwise the right half has none.

A sorted half is easy to reason about: the target is inside it exactly when it lies between that half’s endpoints. If it is, continue there; if it is not, the target can only be in the other half. Either way we discard half the range per step, just like ordinary binary search.

Algorithm.

  1. lo = 0, hi = n - 1.
  2. While lo ≤ hi: compute mid. If nums[mid] == target, return mid.
  3. If nums[lo] ≤ nums[mid] (left half sorted): if nums[lo] ≤ target < nums[mid], set hi = mid - 1; otherwise lo = mid + 1.
  4. Else (right half sorted): if nums[mid] < target ≤ nums[hi], set lo = mid + 1; otherwise hi = mid - 1.
  5. 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;
            else lo = mid + 1;
        } else {                                       // right half mid..hi is sorted
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

Dry run on Example 1, target = 0:

lo hi mid nums[mid] sorted half target inside it? action
0 6 3 7 left [4..7] no lo = 4
4 6 5 1 left [0..1] yes (0 ≤ 0 < 1) hi = 4
4 4 4 0   match return 4

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

The ≤ in nums[lo] ≤ nums[mid] is essential. When only two elements remain, lo == mid, and the “left half” is the single element nums[lo], which is trivially sorted. With < instead, the code would treat the right half as sorted even when it is not, for example on [3, 1] with target 1.

Edge cases and pitfalls