33. Search in Rotated Sorted Array

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

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 an ascending array that is possibly rotated.
• -10^4 <= target <= 10^4

Approach

Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
  let l = 0, r = nums.length - 1;   

  while (l <= r){
    let mid = Math.floor((l + r)/2);
    if (target === nums[mid]) {
      return mid
    }

    // Left sorted portion
    if (nums[l] <= nums[mid]){
      if (target > nums[mid] || target < nums[l]){
        l = mid + 1;
      }else{
        r = mid - 1;
      }
    }
    // Right sorted portion
    else{
      if(target < nums[mid] || target > nums[r]){
        r = mid - 1; 
      }else{
        l = mid + 1;
      }
    }
  }
  return -1;
};

Explanation