Search In Rotated Sorted Array

The problem

nums held different integers in increasing order and was then rotated: some of its first values, possibly none, were moved to the end without changing their order. For example, 0, 1, 2, 4, 5, 6, 7 can become 4, 5, 6, 7, 0, 1, 2. Return the position of target in nums, counting from 0, or -1 if target is not in it.

What to write

function solve(nums: number[], target: number): number

Input
nums = [4,5,6,7,0,1,2]
target = 0

Output
4

Input
nums = [4,5,6,7,0,1,2]
target = 3

Output
-1

Constraints

1 ≤ nums.length ≤ 5000.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   With at most 5,000 values, checking every position would pass. But the array is not shuffled. Its values were in increasing order before the rotation, so from left to right they still rise everywhere except at one spot at most, where they fall back to the smallest value.

2. Hint 2: Ask a smaller question

   Cut [4, 5, 6, 7, 0, 1, 2] into two pieces at any position and look at each piece. Is the piece in increasing order? Try three different cuts. What is true of the two pieces every time?

3. Hint 3: Name the pattern

   The values fall at most once, so whenever you split a range in two, at least one half is in plain increasing order. For that half, comparing target with its first and last value tells you whether target can be inside. One look at the middle then removes about half of the positions: binary search on a sorted range. Read the lesson on binary search on a sorted range.

4. Hint 4: State the invariant

   If target is in the array, its position is inside the range you keep. Each round, find the half that is in order. When target lies between that half's first and last value, keep that half. Otherwise keep the other one.

5. Hint 5: Sketch the pseudocode

   low = 0, high = last position. While low <= high: mid = middle. If nums[mid] is the target, return mid. If nums[low] <= nums[mid]: go left (high = mid - 1) when nums[low] <= target < nums[mid], else go right (low = mid + 1). Otherwise: go right when nums[mid] < target <= nums[high], else go left. Return -1.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

At least one half of every search range is sorted. Decide whether the target belongs to that half before discarding it.

The slow way

Look at every position from left to right and return the one that holds target, or -1 after the last. It is correct, and with 5,000 values it even passes. But it can take as many looks as there are values, and it makes no use of the order the values still have.

The insight

A rotated array has one drop at most: the spot where its largest value is followed by its smallest. Split any range in the middle and the drop is in one half at most, so the other half is in plain increasing order. A half in order holds only values between its two ends, so two comparisons tell whether target can be in it.

Step by step

1. Keep a range of positions that can still hold the target. At the start any position could hold the target. A position leaves the range only when the comparisons show that the target cannot be there.
2. Look at the middle value: if it is the target, return its position. The middle splits the range into two halves of about the same size, so ruling one out removes about half of the positions. If the middle value is the target, the search is over.
3. Compare the left end with the middle to see which half is in order. A left end that is not above the middle value means the drop is not between them, so the left half is in order. Otherwise the drop is in the left half, and the right half is in order.
4. Left half in order: keep it only if the target is between its ends. A half in order holds exactly the values that lie between its two ends. So a target between them can only be in this half, and any other target can only be in the right half.
5. Right half in order: keep it only if the target is between its ends. The same test on the other side. The right half runs in order from the middle value to the right end, so a target outside those two values can only be in the left half.
6. The range is empty, so the target is not in the array. A position was dropped only when the target could not be there. Once no position is left, the target is nowhere in the array, and the answer is -1.

The same numbered steps are the comments in each solution.

function solve(nums, target) {
  // 1. Keep a range of positions that can still hold the target
  let l = 0,
    r = nums.length - 1;
  while (l <= r) {
    // 2. Look at the middle value: if it is the target, return its position
    const m = (l + r) >>> 1;
    if (nums[m] === target) return m;
    // 3. Compare the left end with the middle to see which half is in order
    if (nums[l] <= nums[m]) {
      // 4. Left half in order: keep it only if the target is between its ends
      if (nums[l] <= target && target < nums[m]) r = m - 1;
      else l = m + 1;
    } else {
      // 5. Right half in order: keep it only if the target is between its ends
      if (nums[m] < target && target <= nums[r]) l = m + 1;
      else r = m - 1;
    }
  }
  // 6. The range is empty, so the target is not in the array
  return -1;
}

function solve(nums: number[], target: number): number {
  // 1. Keep a range of positions that can still hold the target
  let l = 0,
    r = nums.length - 1;
  while (l <= r) {
    // 2. Look at the middle value: if it is the target, return its position
    const m = (l + r) >>> 1;
    if (nums[m] === target) return m;
    // 3. Compare the left end with the middle to see which half is in order
    if (nums[l] <= nums[m]) {
      // 4. Left half in order: keep it only if the target is between its ends
      if (nums[l] <= target && target < nums[m]) r = m - 1;
      else l = m + 1;
    } else {
      // 5. Right half in order: keep it only if the target is between its ends
      if (nums[m] < target && target <= nums[r]) l = m + 1;
      else r = m - 1;
    }
  }
  // 6. The range is empty, so the target is not in the array
  return -1;
}

def solve(nums, target):
    # 1. Keep a range of positions that can still hold the target
    left, right = 0, len(nums) - 1
    while left <= right:
        # 2. Look at the middle value: if it is the target, return its position
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        # 3. Compare the left end with the middle to see which half is in order
        if nums[left] <= nums[mid]:
            # 4. Left half in order: keep it only if the target is between its ends
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # 5. Right half in order: keep it only if the target is between its ends
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    # 6. The range is empty, so the target is not in the array
    return -1

Example 1, traced

Input
nums = [4,5,6,7,0,1,2]
target = 0

Output
4

Why it works

If target is in the array, its position is always inside the range. Each round finds a half that is in order and uses its two ends to tell, for certain, which half cannot hold target. Only that half is dropped, along with the middle value, which was checked. The range gets smaller every round, so the search ends.

Time and space

Time O(log n), extra space O(1). Each round makes a fixed number of comparisons and keeps at most half of the range. Halving n positions until none is left takes about log n rounds, so the time is O(log n). Only the two ends of the range and the middle are stored: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Do not choose the half from the middle value alone, as you would in a sorted array. In example 1 the target 0 is below the middle value 7 but sits to its right, and such a search returns -1.
• Compare the left end with the middle using "at most", not "below". In a range of two positions the middle is the left end itself. With "below", [3, 1] and a target of 1 returns -1 instead of 1.
• The target can be the first value of a left half in order: that comparison needs "at least", not "above". With "above", example 1 returns -1: in its second round that half is 0, 1 and the target is 0.

Pattern

Binary search on a sorted range. Builds on Binary Search and Find Minimum In Rotated Sorted Array.

Keep going