This is the 15th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Topic describes

The integer array NUMs is sorted in ascending order, with different values in the array.

Before passing to the function, nums is rotated on some previously unknown subscript k (0 <= k < nums.length), Make the array [nums [k], nums [k + 1),…, nums] [n – 1, nums [0], nums [1],…, nums [k – 1]] (subscript starting from 0). ,1,2,4,5,6,7 [0], for example, in the subscript 3 after rotation may become,5,6,7,0,1,2 [4].

Give you the rotated array nums and an integer target, return its subscript if nums contains the target value, otherwise -1.

  • Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0 output: 4Copy the code
  • Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3 output: -1Copy the code
  • Example 3:
Input: nums = [1], target = 0 Output: -1Copy the code
  • Tip:
1 <= nums.length <= 5000-10 ^4 <= nums[I] <= 10^4 Each value in NUMs is uniqueCopy the code

Implementation approach

The input parameter nums is a rotated array in ascending order. There is a peak in the middle of the rotated array. The left and right parts of the rotated array are arranged in ascending order. Each access to the nums (mids) and nums [left], if is greater than the left said the left part [left, mid] is an ordered array, if less than left [mids, right] is ordered, and then determine whether a target in order interval and the continued to binary search within the range, Otherwise, search in another interval until target returns or the left and right pointer overlap returns -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) {
        let mid = left + Math.floor((right - left) / 2)
        if (nums[mid] == target) {
            return mid
        }
        if (nums[mid] >= nums[left]) { // The left side is ordered
            if (target <= nums[mid] && target >= nums[left]) {
                //target in [nums[left],nums[mid]
                right = mid - 1
            } else {
                / / reverse
                left = mid + 1}}else { // The right-hand side is ordered
            if (target >= nums[mid] && target <= nums[right]) {
                left = mid + 1
            } else {
                right = mid - 1}}}return -1
};
Copy the code