已知存在一个按非降序排列的整数数组 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,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

示例 1：

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

示例 2：

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


提示：

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转

  • -104 <= target <= 104


    进阶：

  • 这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。

  • 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

    解法一：二分法

    解法基本同 33题
    因为数组中有可能出现重复元素，如果当前 left 与 mid 或 mid 与 right 相等的话，我们没办法判定单调区间，所以我们需要相对应的收缩边界即可。
    1. func search(nums []int, target int) bool {
    2.   n := len(nums)
    3.   left, right := 0, n-1
    4.   for left <= right {
    5.       mid := left + (right-left)>>1
    6.       if nums[mid] == target {
    7.           return true
    8.       }
    9.       if nums[mid] > nums[left] {
    10.           if nums[left] <= target && target < nums[mid] {
    11.               right = mid - 1
    12.           } else {
    13.               left = mid + 1
    14.           }
    15.       } else if nums[mid] < nums[right] {
    16.           if nums[mid] < target && target <= nums[right] {
    17.               left = mid + 1
    18.           } else {
    19.               right = mid - 1
    20.           }
    21.       } else {
    22.           if nums[mid] == nums[left] {
    23.               left++
    24.           }
    25.           if nums[mid] == nums[right] {
    26.               right--
    27.           }
    28.       }
    29.   }
    30.   return false
    31. }
  1. function search(nums: number[], target: number): boolean {
  2.   let left = 0
  3.   let right = nums.length - 1
  4.   while(left < right) {
  5.     let mid = left + (right - left >> 1)
  6.     if (nums[mid] === nums[right]) {
  7.       right -= 1
  8.     } else if (nums[mid] < nums[right]) {
  9.       if (nums[mid] < target && target <= nums[right]) {
  10.         left = mid + 1
  11.       } else {
  12.         right = mid
  13.       }
  14.     } else {
  15.       if (nums[left] <= target && target <= nums[mid]) {
  16.         right = mid
  17.       } else {
  18.         left = mid + 1
  19.       }
  20.     }
  21.   }
  22.   return nums[left] === target
  23. };