Search in a Rotated Sorted Array
An array of distinct integers was sorted in ascending order and then rotated: some number of elements were taken off the front and appended to the back, keeping their order. For example, [1, 2, 4, 5, 7, 9] rotated by three positions becomes [5, 7, 9, 1, 2, 4]. The rotation may also be zero, leaving the array fully sorted.
Given the rotated array nums and an integer target, return the index of target in nums, or -1 if it is not there.
Your solution must run in O(log n) time. You don't know how far the array was rotated.
Constraints
1 <= nums.length <= 5000-10^4 <= nums[i], target <= 10^4- All values in
numsare distinct. numsis an ascending array rotated by an unknown amount (possibly zero).
Examples
Example 1
Input: nums = [5,7,9,1,2,4], target = 2 Output: 4
The sorted array [1, 2, 4, 5, 7, 9] was rotated so that it starts at 5. The target 2 is at index 4.
Example 2
Input: nums = [5,7,9,1,2,4], target = 6 Output: -1
6 isn't in the array.
Example 3
Input: nums = [1,2,3,4,5], target = 4 Output: 3
A rotation by zero positions leaves the array fully sorted; that is allowed too.
JavaScript you'll use: Numbers, Math and integer tricks Arrays: create, read, update
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
function searchRotated(nums, target) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.