本期精選題解由我們的用戶“LukeLee ”傾情撰寫，一起來看看吧！

33. 搜索旋轉排序數組（點擊查看題目）

題目描述

假設按照升序排序的數組在預先未知的某個點上進行了旋轉。

( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。

搜索一個給定的目標值，如果數組中存在這個目標值，則返回它的索引，否則返回 -1 。

你可以假設數組中不存在重複的元素。

你的算法時間複雜度必須是 O(log n) 級別。

示例 1:

示例 2:

解決方案

以二分搜索為基本思路

簡要來說：

• nums[0] <= nums[mid]（0 - mid不包含旋轉）且 nums[0] <= target <= nums[mid] 時 high 向前規約；
• nums[mid] < nums[0]（0 - mid包含旋轉），target <= nums[mid] < nums[0] 時向前規約（target 在旋轉位置到 mid 之間）
• nums[mid] < nums[0]，nums[mid] < nums[0] <= target 時向前規約（target 在 0 到旋轉位置之間）
• 其他情況向後規約

也就是說 nums[mid] < nums[0]，nums[0] > target，target > nums[mid] 三項均為真或者只有一項為真時向後規約。

原文的分析是：

注意到原數組為有限制的有序數組（除了在某個點會突然下降外均為升序數組）

• if nums[0] <= nums[I] 那麼 nums[0] 到 nums[i] 為有序數組,那麼當 nums[0] <= target <= nums[i]時我們應該在 0 - i 範圍內查找；
• if nums[i] < nums[0] 那麼在 0 - i 區間的某個點處發生了下降（旋轉），那麼 I + 1 到最後一個數字的區間為有序數組，並且所有的數字都是小於 nums[0] 且大於 nums[i]，當 target 不屬於 nums[0] 到 nums[i] 時（target <= nums[i] < nums[0] or nums[i] < nums[0] <= target），我們應該在 0 - i 區間內查找。

上述三種情況可以總結如下：

所以我們進行三項判斷：

(nums[0] <= target)， (target <= nums[i]) ，(nums[i] < nums[0])，現在我們想知道這三項中有哪兩項為真（明顯這三項不可能均為真或均為假（因為這三項可能已經包含了所有情況））

所以我們現在只需要區別出這三項中有兩項為真還是隻有一項為真。

使用 “異或” 操作可以輕鬆的得到上述結果（兩項為真時異或結果為假，一項為真時異或結果為真，可以畫真值表進行驗證）

之後我們通過二分查找不斷做小 target 可能位於的區間直到 low==high，此時如果 nums[low]==target 則找到了，如果不等則說明該數組裡沒有此項。

C++ 實現

閱讀更多 力扣LeetCode 的文章

關鍵字: 算法 排序 數組