33. Search in Rotated Sorted Array

Link: https://leetcode.com/problems/search-in-rotated-sorted-array

Description: Search for a target in a rotated sorted array.

Solution:

We can use binary search to find the target in the rotated sorted array. We can start with the left and right pointers at the beginning and end of the array. We can find the mid element and check if the mid element is equal to the target. If the mid element is equal to the target, we can return the mid index. If the left element is less than or equal to the mid element, we can check if the target is between the left and mid elements. If the target is between the left and mid elements, we can move the right pointer to the mid - 1 element. If the target is not between the left and mid elements, we can move the left pointer to the mid + 1 element. If the left element is greater than the mid element, we can check if the target is between the mid and right elements. If the target is between the mid and right elements, we can move the left pointer to the mid + 1 element. If the target is not between the mid and right elements, we can move the right pointer to the mid - 1 element. We can continue this process until the left pointer is less than or equal to the right pointer. If the target is not found, we can return -1.

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

  while (left <= right) {
    const m = left + Math.floor((right - left) / 2)

    if (nums[m] === target) {
      return m
    }

    // Determine if we're in the rotated part or the sorted part
    if (nums[left] <= nums[m]) {
      // We're in the left (sorted) part
      if (nums[left] <= target && nums[m] > target) {
        right = m - 1
      } else {
        left = m + 1
      }
    } else {
      // We're in the right (rotated) part
      if (target > nums[m] && target <= nums[right]) {
        left = m + 1
      } else {
        right = m - 1
      }
    }
  }
  return -1
}