1
class Solution {
public:
bool search(vector<int>& nums, int target) {
int index = -1;
for (int i = 0; i < nums.size() - 1; ++i){
if (nums[i] > nums[i + 1]) index = i;
}
if (index == -1){
index = nums.size() - 1;
}
return binarySearch(nums,target,-1,index) || binarySearch(nums,target,index,nums.size() - 1);
}
bool binarySearch(vector<int>& nums,int target,int l,int r){
//左开右闭
while (l < r){
int mid = l + ((r - l) >> 1) + 1;
if (nums[mid] < target){
l = mid;
}else if (nums[mid] > target){
r = mid - 1;
}else{
return true;
}
}
return false;
}
};
2
class Solution {
public:
bool search(vector<int>& nums, int target) {
//左闭右闭
int start = 0;
int end = nums.size()-1;
while (start <= end){
int mid = start + ((end - start) >> 1);
if (nums[mid] == target) return true;
if (nums[mid] == nums[start]) start++;
else if (nums[mid] >= nums[start]){
//左区间增序
if (nums[mid] > target && target >= nums[start]){
end = mid - 1;
}else{
start = mid + 1;
}
}else{
//右区间增序
if (nums[end] >= target && target > nums[mid]){
start = mid + 1;
}else{
end = mid - 1;
}
}
}
return false;
}
};