LeetCode 33. Search in Rotated Sorted Array (javscript solution)

#javascript #algorithms

Description:

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

Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]. 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 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.

Solution:

Time Complexity : O(log n)
Space Complexity: O(1)

// Binary search
var search = function(nums, target) {
    let left = 0, right = nums.length-1;
    while(left < right){
      const mid = left + Math.floor((right - left)/2)
      if(nums[mid]===target) return mid
      // When middle element is less than the last element
      if (nums[mid] < nums[right]) {
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        } 
        // When middle element is greater than the last element
        else {
            if (target > nums[mid] || target < nums[left]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
    }
    return left
};