This is the 11th day of my participation in Gwen Challenge

The topic of dry

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

Solution: dichotomy

So I rotate the array to get two ascending arrays, so I find the rotation, I split the array in half, and then IF target is greater than the rotated value, I binary search in ARR2, and if target is less than the rotated value, I binary search in ARR1

Code implementation:

Execution time: 76 ms, beating 94.75% of all JavaScript submissions

Memory consumption: 38.7 MB, beating 95.00% of all JavaScript commits

  var search = function (nums, target) {
    // Divide the array into two ascending arrays by rotation, determine which array target is in according to the value of target, and then perform binary search
    let length = nums.length
    let theGapNumber
    for (let i = 0; i < length; i++) {
      if (nums[i] > nums[i + 1]) {
        theGapNumber = i + 1}}let arr1 = nums.slice(0, theGapNumber)
    let arr2 = nums.slice(theGapNumber, length)
    if (target > arr1[0]) {
      // use arr1 to find
      return searchOneArea(arr1, target) == -1 ? -1 : searchOneArea(arr1, target)
    } else if (target < arr1[0]) {
      // use arr2 to find
      let targetNum = searchOneArea(arr2, target)
      return targetNum == -1 ? -1 : (arr1.length + targetNum)
    } else {
      return 0}};var searchOneArea = function (nums, target) {
    let max = nums.length - 1;
    let min = 0;
    while (min <= max) {
      let mid = Math.floor((max + min) / 2)
      if (target == nums[mid]) {
        return mid
      } else if (target > nums[mid]) {
        min = mid + 1
      } else {
        max = mid - 1}}return -1
  }
Copy the code