Search in Rotated Sorted Array

Description

You are given an integer array nums sorted in ascending order, and an integer target.

Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

If target is found in the array return its index, otherwise, return -1.

 

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1], target = 0
Output: -1

 

Constraints:

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• All values of nums are unique.
• nums is guranteed to be rotated at some pivot.
• -10^4 <= target <= 10^4

Solution(javascript)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const search = function (nums, target) {
  let left = 0
  let right = nums.length - 1
  let pivot = nums.length - 1
  while (left <= right) {
    const middle = Math.floor(left + (right - left) / 2)
    if (nums[middle] > nums[middle + 1]) {
      pivot = middle
      break
    } else if (nums[middle] < nums[middle - 1]) {
      pivot = middle - 1
      break
    } else if (nums[middle] > nums[0]) {
      left = middle + 1
    } else {
      right = middle - 1
    }
  }
  const search = (left, right) => {
    while (left <= right) {
      const middle = Math.floor(left + (right - left) / 2)
      if (nums[middle] === target) {
        return middle
      } if (nums[middle] < target) {
        left = middle + 1
      } else {
        right = middle - 1
      }
    }
    return -1
  }
  const leftIndex = search(0, pivot)
  return leftIndex > -1 ? leftIndex : search(pivot + 1, nums.length - 1)
}