這是索引二分的第四篇算法，力扣鏈接

已知存在一個按非降序排列的整數數組?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：

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

示例?2：

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

老規矩，先上無腦暴力求解，這道題就是普通的旋轉數組，呈斷崖式遞增，和之前的旋轉數組類似，最本質的區別是當前的題會有重復的場景。

func search(nums []int, target int) bool {for _, num := range nums {if num == target {return true}}return false
}

二分法邏輯其實和旋轉數組也差不多，借此機會復習一下。

這里要分情況討論，先確定target位于的區間。

如果target在左區間（target >= nums[0]）：

- 如果mid位于左區間(nums[mid]?> nums[0])，正常二分法可以找到解。

- 如果mid位于右區間(nums[mid] < nums[0])，盡量使右指針左移到左邊界。

如果target在右邊界（target <?nums(len(nums)-1）

- 如果mid位于左區間(nums[mid]?> nums[0])，盡量使左指針靠近右區間左邊界。

-?如果mid位于右區間(nums[mid] < nums[0])，正常二分法可以求解。

得到代碼如下：

func search(nums []int, target int) bool {l, r := 0, len(nums)-1for l <= r {mid := l + (r-l)/2if nums[mid] == target {return true}if target >= nums[0] {if nums[mid] >= nums[0] {if nums[mid] < target {l = mid + 1} else {r = mid - 1}} else {r = mid - 1}} else {if nums[mid] <= nums[len(nums)-1] {if nums[mid] < target {l = mid + 1} else {r = mid - 1}} else {l = mid + 1}}}return false
}

執行發現，并沒通過，在[1,0,1,1,1]找0的場景報錯了，為什么呢？因為nums[l] == nums[mid] == nums[r] 并不能判斷出來，當前位于哪個區間。

我們可以嘗試 l++ r-- 縮小一下范圍，這樣就沒有左右區間模糊的場景了。

但是還有一個問題，原來的整體坐標邊界參考是nums[0]和nums[len(nums)-1]，在縮小范圍后，也會隨之變化為nums[l] 和 nums[r]。

得到代碼如下：

func search(nums []int, target int) bool {l, r := 0, len(nums)-1for l <= r {mid := l + (r-l)/2if nums[mid] == target {return true}if nums[l] == nums[r] && nums[l] == nums[mid] {l++r--continue}if target >= nums[l] {if nums[mid] >= nums[l] {if nums[mid] < target {l = mid + 1} else {r = mid - 1}} else {r = mid - 1}} else {if nums[mid] <= nums[r] {if nums[mid] < target {l = mid + 1} else {r = mid - 1}} else {l = mid + 1}}}return false
}

邏輯優化：

func search(nums []int, target int) bool {l, r := 0, len(nums)-1for l <= r {mid := l + (r-l)/2if nums[mid] == target {return true}if nums[l] == nums[r] && nums[l] == nums[mid] {l++r--continue}if target >= nums[l] {if nums[mid] >= nums[l] && nums[mid] < target {l = mid + 1} else {r = mid - 1}} else {if nums[mid] <= nums[r] && nums[mid] > target {r = mid - 1} else {l = mid + 1}}}return false
}