題目描述
題目分析
不含重復元素的題解（leetcode33）
這道題也是我們算法課的一道編程題，寫完以后發現當時的思路和現在沒有什么變化，果然是自己啊。我的想法是先判斷區間整體是升序的還是旋轉的，如果是升序的就按照正常的二分查找，如果是旋轉的就判斷中軸的落在了左半升區間還是右半升區間，問題的關鍵在于，旋轉的數組不能簡單因為target和中軸的大小判斷是在左區間還是右區間，因此要分類討論一下。總之，這個思路不是很好，因為沒有有效利用端點的信息，如同官方題解所說，我們是可以直接判斷出target在哪個區間的。每一次中軸會將數組分成兩個部分，至少有一個部分是升序的，我們能夠很簡單的判斷出target是否在那個升序數組中，從而決定在哪個半區間中查找。
我的思路代碼
class Solution {
public:int search(vector<int>& nums, int target) {return bsearch(nums, target, 0, nums.size());}
private:int bsearch(vector<int>& nums, int target, int l, int r) {if (l == r) return -1;int mid = (l + r) >> 1;if (nums[mid] == target) return mid;if (nums[l] <= nums[r - 1]) {//升序區間if (nums[mid] > target) return bsearch(nums, target, l, mid);else return bsearch(nums, target, mid + 1, r);} else {//旋轉區間if (nums[mid] >= nums[l]) {//中心點落在左邊升序區間if (nums[mid] < target) return bsearch(nums, target, mid + 1, r);else {int lr = bsearch(nums, target, l, mid);int rr = bsearch(nums, target, mid + 1, r);if (lr == -1) {if (rr == -1) return -1; else return rr;} else return lr;}} else {//中心點落在右邊升序區間if (nums[mid] > target) return bsearch(nums, target, l ,mid);else {int lr = bsearch(nums, target, l, mid);int rr = bsearch(nums, target, mid + 1, r);if (lr == -1) {if (rr == -1) return -1; else return rr;} else return lr;}}}}
};
按照官方題解寫的代碼
class Solution {
public:int search(vector<int>& nums, int target) {int l = 0, r = nums.size(), mid;while (l < r) {mid = (l + r) >> 1;if (nums[mid] == target) return mid;if (nums[mid] >= nums[l]) {//左半區間是升序if (target >= nums[l] && target < nums[mid]) r = mid;else l = mid + 1;} else {//右半區間是升序if (target > nums[mid] && target <= nums[r - 1]) l = mid + 1;else r = mid;}}return -1;}
};
剛才看了一下題解，發現它總是和nums[0]和nums[n-1]比較，厲害。
