問題鏈接
LeetCode 33. Search in Rotated Sorted Array
題目解析
給定一個 “升序” 的 無重復 數組,從中尋找目標值。“升序”:旋轉后的升序,例如 [4,5,1,2,3]。
時間限制:\(O(lgN)\)。
解題思路
題目要求在 \(O(lgN)\) 時間內找到目標值,很容易想到二分法。如果是普通的升序,普通的二分即可解決問題。題目中提到的旋轉后的升序,我們不知道其“旋轉點”在哪,那么有什么特點呢?以題目例子分析:
對于普通升序數組[0,1,2,3,4,5,6,7],其旋轉后可能情況有[1,2,3,4,5,6,7,0]、[2,3,4,5,6,7,0,1][3,4,5,6,7,0,1,2]、[4,5,6,7,0,1,2,3]、[5,6,7,0,1,2,3,4]、[6,7,0,1,2,3,4,5]、[7,0,1,2,3,4,5,6]七種情況。
leetcode 53,二分法的關鍵在于取中間值后,與目標值比較,判斷左半段還是右半段。觀察上述八種情況,可以發現以中間值為界,左右兩部分總有一段是絕對升序的。當 nums[mid] < nums[right] 時,右半段絕對升序;當 nums[mid] > nums[right] 時,左半段絕對升序。
仔細想想,這個規律很簡單的,不需要證明。
旋轉有序的特點已經找到了,我們只需要判斷目標值是否在絕對升序的范圍內,就可以確定二分的邊界了。
參考代碼
class Solution {
public:int search(vector<int>& nums, int target) {int len = nums.size();if (len < 1) return -1;int left = 0, right = len-1;while(left <= right) {int mid = (left + right) / 2;if (nums[mid] == target) return mid;if (nums[mid] < nums[right]) {if (nums[mid] < target && nums[right] >= target) left = mid+1;else right = mid-1;}else {if (nums[left] <= target && nums[mid] > target) right = mid-1;else left = mid+1;}}return -1;}
};
相似題目
LeetCode 81. Search in Rotated Sorted Array II
LeetCode All in One題解匯總(持續更新中...)
本文版權歸作者AlvinZH和博客園所有,歡迎轉載和商用,但未經作者同意必須保留此段聲明,且在文章頁面明顯位置給出原文連接,否則保留追究法律責任的權利.