📑 题目：81. 搜索旋转排序数组 II

🚀 本题 LeetCode 传送门

题目大意

假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

进阶:

• 这是搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。
• 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

解题思路

• 给出一个数组，数组中本来是从小到大排列的，并且数组中有重复数字。但是现在把后面随机一段有序的放到数组前面，这样形成了前后两端有序的子序列。在这样的一个数组里面查找一个数，设计一个 O(log n) 的算法。如果找到就输出 true，如果没有找到，就输出 false 。
• 这一题是第 33 题的加强版，实现代码完全一样，只不过输出变了。这一题输出 true 和 false 了。具体思路见第 33 题。

代码

package leetcode
func search(nums []int, target int) bool {
 if len(nums) == 0 {
  return false
 }
 low, high := 0, len(nums)-1
 for low <= high {
  mid := low + (high-low)>>1
  if nums[mid] == target {
   return true
  } else if nums[mid] > nums[low] { // 在数值大的一部分区间里
   if nums[low] <= target && target < nums[mid] {
    high = mid - 1
   } else {
    low = mid + 1
   }
  } else if nums[mid] < nums[high] { // 在数值小的一部分区间里
   if nums[mid] < target && target <= nums[high] {
    low = mid + 1
   } else {
    high = mid - 1
   }
  } else {
   if nums[low] == nums[mid] {
    low++
   }
   if nums[high] == nums[mid] {
    high--
   }
  }
 }
 return false
}