leetcode 53，LeetCode 33. Search in Rotated Sorted Array

問題鏈接

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和博客園所有，歡迎轉載和商用，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利.

---