Find a target in a rotated sorted array in O(log n)
A chat client keeps the IDs of recent messages in a fixed-size ring buffer. The IDs were written in ascending order, but because the buffer wraps around, the array you receive is a sorted array that has been rotated: some prefix was moved to the end. For example, [3, 9, 21, 40, 52, 67] rotated by 3 is [40, 52, 67, 3, 9, 21].
Implement searchRotated(nums, target). It returns the index of target in nums, or -1 if it is not there.
searchRotated(nums, target) // => index or -1
nums holds distinct integers that were sorted ascending and then rotated by an unknown amount between 0 and nums.length - 1. A rotation of 0 means the array is simply sorted.indexOf, includes, findIndex or a for...of loop) fails on large inputs.nums. Reading nums.length is free.-1.searchRotated([40, 52, 67, 3, 9, 21], 9);
// => 4
searchRotated([40, 52, 67, 3, 9, 21], 52);
// => 1
searchRotated([40, 52, 67, 3, 9, 21], 10);
// => -1
searchRotated([-8, -2, 5, 11], 11);
// => 3 (not rotated)
searchRotated([7, 1], 1);
// => 1
searchRotated([], 4);
// => -1