代码有几个用例过不了,不知道为什么
/*
* 二分算法
* 两次二分
* 先通过二分,找出旋转后的分界点
* 然后比较target的值,在左区间或者右区间再次进行二分
*
*/
#include <iostream>
#include <vector>
using namespace std;
int searchNum(vector<int>& nums, int target){
if(nums.size() == 0) return -1;
if(nums.size() == 1){
if(nums[0] == target) return 0;
else return -1;
}
int index = 0; // target的索引
// 先通过二分,找出旋转后的分界点(右分界点)
// [>=x, <x]
int n = nums.size();
int x = nums[0];
int l = 0, r = n-1;
while(l<r){
int mid = (l+r)/2;
if(nums[mid]<x) r = mid; // [l, mid][mid+1, r]
else l = mid+1;
}
// 右分界点
int p = l;
// target在左区间中,[0, p-1]
if(target >= x){
int l = 0, r = p-1;
// [<target][>=target]
while(l<r){
int mid = (l+r)/2;
if(nums[mid]>=target) r = mid; // [l, mid][mid+1, r]
else l = mid+1;
}
index = r;
}
// target在右区间中,[p, n-1]
else{
// [<<target][>=target]
int l = p, r = n-1;
while(l<r){
int mid = (l+r)/2;
if(nums[mid]>=target) r = mid; // [l, mid][mid+1, r]
else l = mid+1;
}
index = r;
}
if(nums[index] == target) return index;
else return -1;
}
int main(){
vector<int> nums{1,3};
int target = 3;
cout<<searchNum(nums, target)<<endl;
return 0;
}