RotatedSortedArray.js

// 33. Search in Rotated Sorted Array

// 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 = 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

function search(nums, target){
    let left = 0
    let right = nums.length-1

    while(left <= right){
        let middleIndex = Math.floor((left + right)/2)
        if(target === nums[middleIndex]){
            return middleIndex
        }
        // check to see we are in the left array. 
        if(nums[left] <= nums[middleIndex]){
            if(target > nums[middleIndex] || nums[left] > target){
                left = middleIndex+1
            }else{
                right = middleIndex-1
            }
        }else{
            if(target < nums[middleIndex] || nums[right] < target){
                right = middleIndex-1
            }else{
                left = middleIndex+1
            }
        }
    }
    return -1
}

console.log(search([4,5,6,7,0,1,2], 0))//4
console.log(search([4,5,6,7,0,1,2], 3))//-1
console.log(search([1], 0))//-1