2021-09-26：搜尋旋轉排序陣列。整數陣列 nums 按升序排列，陣列中

2021-09-26：搜尋旋轉排序陣列。整數陣列 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 。力扣33。

福大大答案2021-09-26：

二分法。

時間複雜度：O（logN）。極端情況下是O（N）。

空間複雜度：O（1）。

程式碼用golang編寫。程式碼如下：

package mainimport “fmt”func main（） { arr ：= ［］int{4， 5， 6， 7， 0， 1， 2} num ：= 0 ret ：= search（arr， num） fmt。Println（ret）}// arr，原本是有序陣列，旋轉過，而且左部分長度不知道// 找num// num所在的位置返回func search（arr ［］int， num int） int { L ：= 0 R ：= len（arr） - 1 M ：= 0 for L <= R { // M = L + （（R - L） >> 1） M = （L + R） / 2 if arr［M］ == num { return M } // arr［M］！= num // ［L］ == ［M］ == ［R］！= num 無法二分 if arr［L］ == arr［M］ && arr［M］ == arr［R］ { for L ！= M && arr［L］ == arr［M］ { L++ } // 1） L == M L。。。M 一路都相等 // 2）從L到M終於找到了一個不等的位置 if L == M { // L。。。M 一路都相等 L = M + 1 continue } } // 。。。 // arr［M］！= num // ［L］［M］［R］不都一樣的情況，如何二分的邏輯 if arr［L］！= arr［M］ { if arr［M］ > arr［L］ { // L。。。M 一定有序 if num >= arr［L］ && num < arr［M］ { // 3 ［L］ == 1 ［M］ = 5 L。。。M - 1 R = M - 1 } else { // 9 ［L］ == 2 ［M］ = 7 M。。。 R L = M + 1 } } else { // ［L］ > ［M］ L。。。。M 存在斷點 if num > arr［M］ && num <= arr［R］ { L = M + 1 } else { R = M - 1 } } } else { /// ［L］［M］［R］不都一樣，［L］ === ［M］ -> ［M］！=［R］ if arr［M］ < arr［R］ { if num > arr［M］ && num <= arr［R］ { L = M + 1 } else { R = M - 1 } } else { if num >= arr［L］ && num < arr［M］ { R = M - 1 } else { L = M + 1 } } } } return -1}

執行結果如下：

！［圖片］（https：//img-blog。csdnimg。cn/62bfd69839ea470eb5f01e0dfbf6ef02。png？x-oss-proces