[Leetcode] 33. Search in Rotated Sorted Array

Table of Contents

Description

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 in nums 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

Constraints:

• $1 \leq \text{nums.length} \leq 5000$
• $-10^4 \leq \text{nums[i]} \leq 10^4$
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• $-10^4 \leq \text{target} \leq 10^4$

Approach

Because the requirement is to limit the solution to $O(\log n)$ complexity, we use binary search. The main idea is to repeatedly divide the array in half and determine which half is sorted. By comparing the target with the sorted half, we can decide whether to continue searching in the left(green) or right(red) half. This process is repeated until the target is found or the search space is empty.

Solution

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

  while (left <= right) {
    mid = Math.floor((left + right) / 2);

    // Check if mid element is the target
    if (nums[mid] === target) return mid;

    // Determine which part is sorted
    if (nums[mid] >= nums[left]) {
      // Left part is sorted
      if (nums[left] <= target && nums[mid] >= target) {
        // target is within the sorted left part
        right = mid - 1;
      } else {
        // target is not in the sorted left part, search right part
        left = mid + 1;
      }
    } else {
      // Right part is sorted
      if (nums[right] >= target && nums[mid] <= target) {
        // target is within the sorted right part
        left = mid + 1;
      } else {
        // target is not in the sorted right part, search left part
        right = mid - 1;
      }
    }
  }

  // target not found
  return -1;
};

Complexity Analysis

Time Complexity

The time complexity is $O(\log n)$, where $n$ is the length of the input array nums. This is because we are halving the search space in each iteration of the while loop.

Space Complexity

The space complexity is $O(1)$, as we are only using a constant amount of extra space for variables.