Question

33. Search in Rotated Sorted Array

中文文档

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_ 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 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• -104 <= target <= 104

Solutions

Solution 1: Binary Search

We use binary search to divide the array into two parts, $[left,.. mid]$ and $[mid + 1,.. right]$. At this point, we can find that one part must be sorted.

Therefore, we can determine whether $target$ is in this part based on the sorted part:

• If the elements in the range $[0,.. mid]$ form a sorted array:
  • If $nums[0] \leq target \leq nums[mid]$, then our search range can be narrowed down to $[left,.. mid]$;
  • Otherwise, search in $[mid + 1,.. right]$;
• If the elements in the range $[mid + 1, n - 1]$ form a sorted array:
  • If $nums[mid] \lt target \leq nums[n - 1]$, then our search range can be narrowed down to $[mid + 1,.. right]$;
  • Otherwise, search in $[left,.. mid]$.

The termination condition for binary search is $left \geq right$. If at the end we find that $nums[left]$ is not equal to $target$, it means that there is no element with a value of $target$ in the array, and we return $-1$. Otherwise, we return the index $left$.

The time complexity is $O(\log n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.

class Solution:
  def search(self, nums: List[int], target: int) -> int:
    n = len(nums)
    left, right = 0, n - 1
    while left < right:
      mid = (left + right) >> 1
      if nums[0] <= nums[mid]:
        if nums[0] <= target <= nums[mid]:
          right = mid
        else:
          left = mid + 1
      else:
        if nums[mid] < target <= nums[n - 1]:
          left = mid + 1
        else:
          right = mid
    return left if nums[left] == target else -1

class Solution {
  public int search(int[] nums, int target) {
    int n = nums.length;
    int left = 0, right = n - 1;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (nums[0] <= nums[mid]) {
        if (nums[0] <= target && target <= nums[mid]) {
          right = mid;
        } else {
          left = mid + 1;
        }
      } else {
        if (nums[mid] < target && target <= nums[n - 1]) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
    }
    return nums[left] == target ? left : -1;
  }
}

class Solution {
public:
  int search(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0, right = n - 1;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (nums[0] <= nums[mid]) {
        if (nums[0] <= target && target <= nums[mid])
          right = mid;
        else
          left = mid + 1;
      } else {
        if (nums[mid] < target && target <= nums[n - 1])
          left = mid + 1;
        else
          right = mid;
      }
    }
    return nums[left] == target ? left : -1;
  }
};

func search(nums []int, target int) int {
  n := len(nums)
  left, right := 0, n-1
  for left < right {
    mid := (left + right) >> 1
    if nums[0] <= nums[mid] {
      if nums[0] <= target && target <= nums[mid] {
        right = mid
      } else {
        left = mid + 1
      }
    } else {
      if nums[mid] < target && target <= nums[n-1] {
        left = mid + 1
      } else {
        right = mid
      }
    }
  }
  if nums[left] == target {
    return left
  }
  return -1
}

function search(nums: number[], target: number): number {
  const n = nums.length;
  let left = 0,
    right = n - 1;
  while (left < right) {
    const mid = (left + right) >> 1;
    if (nums[0] <= nums[mid]) {
      if (nums[0] <= target && target <= nums[mid]) {
        right = mid;
      } else {
        left = mid + 1;
      }
    } else {
      if (nums[mid] < target && target <= nums[n - 1]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
  }
  return nums[left] == target ? left : -1;
}

impl Solution {
  pub fn search(nums: Vec<i32>, target: i32) -> i32 {
    let mut l = 0;
    let mut r = nums.len() - 1;
    while l <= r {
      let mid = (l + r) >> 1;
      if nums[mid] == target {
        return mid as i32;
      }

      if nums[l] <= nums[mid] {
        if target < nums[mid] && target >= nums[l] {
          r = mid - 1;
        } else {
          l = mid + 1;
        }
      } else {
        if target > nums[mid] && target <= nums[r] {
          l = mid + 1;
        } else {
          r = mid - 1;
        }
      }
    }
    -1
  }
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  const n = nums.length;
  let left = 0,
    right = n - 1;
  while (left < right) {
    const mid = (left + right) >> 1;
    if (nums[0] <= nums[mid]) {
      if (nums[0] <= target && target <= nums[mid]) {
        right = mid;
      } else {
        left = mid + 1;
      }
    } else {
      if (nums[mid] < target && target <= nums[n - 1]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
  }
  return nums[left] == target ? left : -1;
};