Skip to main content

Search in Rotated Sorted Array

Problem statement​

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • All values of nums are unique.
  • nums is an ascending array that is possibly rotated.
  • -104 <= target <= 104

My solution​

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left < right) {
       let mid =  Math.floor((right + left)/2)
       
       // console.log(left, right, mid)
       
       if (nums[left] < nums[mid]) {
           // console.log("TOP")
           if (nums[left] <= target && target <= nums[mid]) {
               right = mid;
           } else {
               left = mid + 1;
           }
       } else {
           // console.log("BOTTOM")
           if (nums[mid + 1] <= target && target <= nums[right]) {
               left = mid + 1
           } else {
               right = mid
           }
       }
        
        // console.log(">>>>",left, right, mid)
    }
    
    // console.log("left", left)
    
    return nums[left] === target ? left : -1
};