Find Element in Rotated ArrayLoading saved progress…

Find Element in Rotated Array

You're given an ascending sorted array of integers that someone took and rotated: they cut it at some unknown index and moved the front chunk to the back. So [1, 2, 3, 4, 5] rotated at index 3 becomes [4, 5, 1, 2, 3]. All values are distinct. Implement arrayRotatedFind(nums, target) — return the index of target, or -1 if it isn't there. A linear scan would do it, but it throws away the sorted structure; the bar here is to keep the O(log n) of binary search even though the array is no longer fully sorted.

Signature

// nums:   number[]  — distinct integers, ascending then rotated at an
//                     unknown pivot (the pivot may be 0, i.e. not rotated).
// target: number    — the value to locate.
// returns: number   — the index of target in nums, or -1 if absent.
function arrayRotatedFind(nums, target): number;

Examples

// Rotated: the original [0,1,2,4,5,6,7] was rotated so 4,5,6,7 moved to the front.
arrayRotatedFind([4, 5, 6, 7, 0, 1, 2], 0); // → 4
arrayRotatedFind([4, 5, 6, 7, 0, 1, 2], 3); // → -1  (not present)
// Not rotated at all (pivot 0) — behaves like plain binary search.
arrayRotatedFind([1, 2, 3, 4, 5], 4); // → 3

// Target sits at the pivot (the minimum), at the end, and in a single-element array.
arrayRotatedFind([5, 1, 2, 3, 4], 1); // → 1   (the rotation point / smallest value)
arrayRotatedFind([4, 5, 6, 7, 0, 1, 2], 2); // → 6   (last element)
arrayRotatedFind([42], 42); // → 0

Notes

  • Values are distinct. No duplicates appear in nums. This matters: with duplicates you can't always tell which half is sorted ([1, 1, 1, 0, 1]), which degrades the worst case to O(n). Assume distinctness and keep it O(log n).
  • The pivot is unknown and may be zero. A "rotation" of 0 means the array is just normally sorted. Your code must handle the not-rotated case as naturally as the rotated one.
  • Return the index, not the value or a boolean. On a miss, return -1.
  • Aim for O(log n). A correct linear scan passes the functional tests but misses the point of the question — at each step you should halve the search space, not walk it.
  • Don't worry about an empty array beyond returning -1, non-integer inputs, or NaN targets — inputs are well-formed arrays of distinct integers.
Loading editor…