整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

示例 1：

  1. 输入：nums = [4,5,6,7,0,1,2], target = 0
  2. 输出：4

示例 2：

  1. 输入：nums = [4,5,6,7,0,1,2], target = 3
  2. 输出：-1

示例 3：

  1. 输入：nums = [1], target = 0
  2. 输出：-1


提示：

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转

  • -10^4 <= target <= 10^4


    进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？

    解法一：二分查找

    通过这个题 我们可以学习到二分法其实不需要两边都具有单调性，只要有一遍具有单调性即可。

  • 每次的 mid 无非三种情况，在断点前（所以 [left, mid) 具有单调性）、刚好是要找的结果、在端点后（所以 (mid, right] 具有单调性）

  • 所以我们要考虑的是在单调区间内的操作即可，另外一个区间的可以再往下划分，始终会得到一个单调区间哦
    • 在断点前时 nums[left] <= target < nums[mid]
    • 在断点后时 nums[mid] < target <= nums[right] 
      1. func search(nums []int, target int) int {
      2. left, right := 0, len(nums)-1
      3. for left <= right {
      4.    mid := left + (right-left)>>1
      5.    if nums[mid] == target {
      6.        return mid
      7.    }
      8.    // mid 在断点前， [left, mid) 递增， (mid, right] 不递增
      9.    // 这里必须用 <= 因为 mid 是不断向下取整，nums 只有俩参数时候  left = mid，且 target >= nums[left] 是放在这个分支处理的。
      10.    if nums[left] <= nums[mid] {
      11.        // target 在 [left, mid) 区间里， 满足二分单调性
      12.        if nums[mid] > target && target >= nums[left] {
      13.            right = mid - 1
      14.        } else {
      15.            // target 在 (mid, right] 区间里，该区间不确定其单调性
      16.            left = mid + 1
      17.        }
      18.    } else {
      19.        // mid 在端点后，[left, mid) 不递增，(mid, right] 递增
      20.        // target 在 (mid, right] 区间里，满足二分单调性
      21.        if nums[mid] < target && target <= nums[right] {
      22.            left = mid + 1
      23.        } else {
      24.            // target 在 [left, mid)区间里，该区间不确定其单调性
      25.            right = mid - 1
      26.        }
      27.    }
      28. }
      29. return -1
      30. }
  1. function search(nums: number[], target: number): number {
  2.   let left = 0
  3.   let right = nums.length - 1
  4.   while(left < right) {
  5.     let mid = left + (right - left >> 1)
  6.     // 注意这里的 <= 因为是  mid 是向下取整的
  7.     if (nums[left] <= nums[mid]) {
  8.       if (nums[left] <= target && nums[mid] >= target) {
  9.         right = mid
  10.       } else {
  11.         left = mid + 1
  12.       }
  13.     } else {
  14.       if (nums[mid] <  target && target <= nums[right]) {
  15.         left = mid + 1
  16.       } else {
  17.         right = mid
  18.       }
  19.     }
  20.   }
  21.   return nums[left] === target ? left : -1
  22. };