[leetcode - Bliend-75 ] 33. Search in Rotated Sorted Array (

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.

给定一个阵列 nums 他会在随机的 index 旋转，比如 [0,1,2,4,5,6,7] 会在 index = 3 的地方发生旋转变成 [4,5,6,7,0,1,2]，找到 target 在旋转过后的 nums 中的 index。

Coding

即使阵列 nums 在随机的 index 发生旋转后，对于旋转的那一点来说，左边右边都还是 sorting 的状态 [4,5,6] 和 [0,1,2] 都是 sorting 的状态，首先先要找到 middle 值并知道 target 目前处于哪一边的 sorting array 中。

/** * @param {number[]} nums * @param {number} target * @return {number} */var search = function(nums, target) {  let l = 0, r = nums.length - 1;  while (l <= r) {      const middle = Math.floor((r - l) / 2) + l;            if (nums[middle] === target) {          return middle;      }      if (nums[l] <= nums[middle]) {        if (target < nums[middle] && target >= nums[l]) {          r = middle - 1;        } else {          l = middle + 1;        }      } else {        if (target > nums[middle] && target <= nums[r]) {          l = middle + 1;        } else {          r = middle - 1;        }      }  }  return -1;};

找到 middle

nums[middle] < target < nums[r]

移动 l 到 middle 右边一格

如果 nums[l] <= target < nums[middle] 代表 target 在左边的 array 中，所以将 r 移动到 middle 左边一格，相反的如果 target 没有小于 nums[l] 或大于 nums[middle] 则代表 target 在右边的 array。如果 nums[middle] < target <= nums[r] 代表 target 在右边的 array 中，将 l 移动到 middle 右边一格，相反的如果 target 没有大于 nums[middle] 或小于 nums[r] 则代表 target 在左边的 array。

Time complexity: O(logn)