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 右邊一格

1. 如果 nums[l] <= target < nums[middle] 代表 target 在左邊的 array 中，所以將 r 移動到 middle 左邊一格，相反的如果 target 沒有小於 nums[l] 或大於 nums[middle] 則代表 target 在右邊的 array。
2. 如果 nums[middle] < target <= nums[r] 代表 target 在右邊的 array 中，將 l 移動到 middle 右邊一格，相反的如果 target 沒有大於 nums[middle] 或小於 nums[r] 則代表 target 在左邊的 array。

Time complexity: O(logn)