Search in Rotated Sorted Array

MediumArray Binary Search

A logging service writes entries with distinct, increasing IDs into a fixed-size ring buffer. Dumping the buffer from slot 0 gives the IDs in ascending order but possibly rotated, because the oldest entry can sit anywhere in the ring: the IDs [3,8,14,20,31] might come out as [20,31,3,8,14]. Where the rotation happened is unknown, and there may be no rotation at all.

Given the dump nums and an ID target, return the index of target in nums, or -1 if it is not in the dump. The lookup must run in O(log n) time.

Example 1

Input: nums = [20,31,3,8,14], target = 8
Output: 3

Explanation: The ascending run restarts at index 2, and 8 sits right after 3.

Example 2

Input: nums = [20,31,3,8,14], target = 25
Output: -1

Explanation: 25 would fall between 20 and 31, but no such ID was logged.

Example 3

Input: nums = [-4,0,6,11], target = 11
Output: 3

Explanation: This dump is not rotated at all, and the same search still works.

Constraints

nums holds between 1 and 5000 IDs.
The IDs are distinct integers from -10^4 to 10^4, and target is in the same range.
nums is an ascending list that may have been rotated.

💡 Hint 1

Split the array at any index mid. At least one of the two halves is sorted normally. How can you tell which one?

💡 Hint 2

If nums[lo] <= nums[mid], the left half is sorted. Then it is easy to check whether target lies inside its value range.

💡 Hint 3

Keep the half that could contain the target and discard the other, exactly like ordinary binary search.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Run binary search on [lo, hi], but at each step first work out which half is sorted. If nums[lo] <= nums[mid], the left half [lo, mid] is in ascending order: the target is there exactly when nums[lo] <= target < nums[mid], so move hi = mid - 1 in that case and lo = mid + 1 otherwise. If instead the right half [mid, hi] is sorted, check nums[mid] < target <= nums[hi] the same way. Either way half of the window disappears, and the distinct values guarantee the sorted-half test is never ambiguous.

Time O(log n)Space O(1)

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

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]) {
                if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function search(nums, target) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit