leetCode81. 搜索旋转排序数组 II

leetCode81. 搜索旋转排序数组 II

---

题目思路

可以二分后的具体思路见我的上篇博客
搜索旋转排序数组

---

代码

class Solution {
public:bool search(vector<int>& nums, int target) {if(nums.empty()) return false;int R = nums.size() - 1;while(R >= 0 && nums[0] == nums[R]) R--;if(R < 0) return nums[0] == target;// 第一次二分，找到两端的临界值int l = 0, r = R;while(l < r){int mid = l + r + 1 >> 1;if(nums[mid] >= nums[0]) l = mid;else r = mid - 1; }if(target >= nums[0]) r = l, l = 0;else l++, r = R;// 第二次二分，找到target的位置while(l < r){int mid = l + r >> 1;if(nums[mid] >= target) r = mid;else l = mid + 1;}return nums[r] == target;}
};

---

方法二：直接暴力搜索，但时间复杂度铁定o(n),二分的话，最坏o(n),所以此题暴力法也差不多，时间复杂度都一样

// 因为用二分法 最欢情况下是o(n),所以不如直接从头遍历一下
class Solution {
public:bool search(vector<int>& nums, int target) {for(auto &v : nums){if(v == target) return true;}return false;}
};