LEETCODE 解題紀錄 #4
33. Search in Rotated Sorted Array
└─解題難度：MEDIUM
獻給所有對 Binary Search 感到苦手的人。
如果你有以下症狀，諸如渾渾噩噩算不清邊界、要等號還是不要等號、選左還選右等等困擾，請盡速前往 LeetCode 教學 Binary Search 篇對症下藥及時根治🚑
題目說明
給定一個整數陣列，要找出目標數字出現在陣列中的索引值，若不存在於陣列中則返回 -1。
與典型的 Binary Search 不同的是，該陣列在輸入前會經過一次程度不一的旋轉。
以 [1,2,3,4,5] 為例，若向右旋轉 1 個位置，則會得到 [5,1,2,3,4]，其中原先最右邊的 5 穿過了邊界來到了新位置 (即最左邊)。
解題分析
由於題目要求時間複雜度須為 O(log N) 以下，因此勢必要使用 Binary Search，在每一輪搜尋時將搜索空間 (Search space) 一次縮小一半。
典型的 Binary Search 題目都是從有序的陣列中進行搜尋，因為在有序的情況下，我們可以透過 left, middle, right 三個點去判斷搜尋的目標在哪一塊子搜索空間內，並排除其他搜索空間。
本題的整數陣列經過旋轉後的數值大小關係可以下圖為例。
假設對兩點 left, right 取中點得到 mid1，我們可以從圖中看出，mid1 的左半部可保證為有序排列，右半部則包含了旋轉造成的切面 (圖中深色虛線)。
透過圖中我們可以歸納出 mid1 的特徵包含了 nums[mid1] ≥ nums[left] 這個條件。
在 mid1 的情況下，我們可以判斷 target 是否存在於 nums[left] 和 nums[mid1] 之間，去決定要保留哪一塊搜索空間 ([left, mid1] 或是 [mid1, right])。
在另一個情況中，若對 left, right 取中點得到 mid2，我們可發現 nums[right] ≥ nums[mid2]，並且可透過判斷 target 是否存在於 nums[mid2] 和 nums[right] 之間去決定要保留的搜索空間。
在這個演算法中，我們只依賴其中一半的子搜索空間去判斷要保留哪一邊，並且被依賴的那半個搜索空間是符合有序條件的那一半。
照這樣看來，一個未經旋轉的有序陣列也適用於這個演算法，因為這個有序陣列的兩個子搜索空間都是有序的，我們只要任選其中一半進行上述之判斷即可知道要保留哪一半。
解決方案
每次對 left, right 取中點 mid 之後，先判斷是 [left, mid] 這個空間有序 (mid1 情況) 還是 [mid, right] 是有序的 (mid2 情況)。
接著按照有序的那半個搜索空間，我們就可以判斷出要如何修改 left 或 right 縮小搜索空間。
