leetcode-cn.com/problems/se…

Answer:

  1. Since arrays are monotonically increasing, this feature can be solved by binary lookup.
  2. The array is rotated from somewhere, so the array is divided from the rotation point, and both parts are monotonically increasing, and all of the first half is larger than the second half.
  3. If the target is before the midpoint of the array, there are two cases:
    • Nums [0] < nums[mid] indicates that the rotation point is in the first half. In this case, you need to determine the rotation point
      • Nums [0] <= target, indicating that target is between 0 and the rotation point
      • Target <= nums[mid], target between rotation point and midpoint
    • Nums [0] < nums[mid] indicates the latter part of the rotation point. In this case, you need to determine further
      • Nums [0] <= target && target < nums[mid], target is between nums[0] and nums[mid]
  4. Once the judgment method is clear, binary lookup can be carried out according to this rule.
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number}* /
var search = function (nums, target) {
  let left = 0; // The left edge of the search
  let right = nums.length - 1; // The right edge of the search

  // Perform binary search and exit the loop when left and right Pointers meet
  while (left <= right) {
    // Take the middle value, the answer must be either side of the middle value
    const mid = (left + right) >> 1;

    // If the median is equal to the target, the search is successful and the index is returned
    if (nums[mid] === target) {
      return mid;
    }

    // Check whether target is in the first half
    if (
      // If the array is rotated in the first half
      // nums[0] is greater than nums[mid], indicating that the rotation point is in the first half
      (
        nums[mid] < nums[0] &&
        (
          // Target is between 0 and rotation point
          nums[0] <= target ||
          // target is between the rotation point and the midpoint
          target <= nums[mid]
        )
      ) ||
      // If the back half of the array is rotated
      // The first half of the array is monotonically incremented
      (
        nums[0] < nums[mid] &&
        // target is between nums[0] and nums[mid]
        nums[0] <= target && target < nums[mid]
      )
    ) {
      // Look forward to target
      right = mid - 1;
    } else {
      // Look for target in the back half
      left = mid + 1; }}// If the loop exits normally, target is not found, and -1 is returned
  return -1;
};
Copy the code