2019独角兽企业重金招聘Python工程师标准>>>
Follow up forSearch in Rotated Sorted Array :What if duplicates are allowed?
Would this affect the run-time complexity?How and Why?
Write a function to determine if a given target is in the array.
允许数组旋转,并且还允许数组重复,这种情况下,还是可以使用二分法来查找目标元素。
如果允许数组中元素重复,在数组旋转之后,a[m]>=a[1]的情况下,1~m之间的数组就不一定是单调递增的。比如{1,3,1,1,1}. 其实只有等于号的情况下,递增性是不确定的。那就需要将=和>分开考虑。
- a[m]>a[1],则在[1,m]之间,数组一定是递增的,就算有重复元素,这一段也还是递增的。
- a[m]=a[1],在[1,m]之间,数组就不一定是递增的了。那就需要查看下一个元素。
解决方案:
class Solution
{
public:
int search(const vector<int>& num,int target)
{
int first = 0;
int last = num.size();
while(first != last)
{
const int mid = first + (last - first)/2;
if(num[mid] == target)
return mid;
if(num[first] < num[mid])
{
if(num[first] <= target && num[mid] > target)
last = mid;
else
first = mid + 1;
}
else if(num[first] > num[mid])
{
if(num[mid]< target && num[last] > target)
first = mid + 1;
else
last = mid;
}
else
{
first+=1;
}
}
return -1;
}
};
测试代码:
#include<iostream>
#include<vector>
using namespace std;
class Solution
{
public:
int search(const vector<int>& num,int target)
{
int first = 0;
int last = num.size();
while(first != last)
{
const int mid = first + (last - first)/2;
if(num[mid] == target)
return mid;
if(num[first] < num[mid])
{
if(num[first] <= target && num[mid] > target)
last = mid;
else
first = mid + 1;
}
else if(num[first] > num[mid])
{
if(num[mid]< target && num[last] > target)
first = mid + 1;
else
last = mid;
}
else
{
first+=1;
}
}
return -1;
}
};
int main(void)
{
vector<int> a;
int target = 1;
a.push_back(4);
a.push_back(5);
a.push_back(5);
a.push_back(6);
a.push_back(6);
a.push_back(7);
a.push_back(7);
a.push_back(1);
a.push_back(2);
a.push_back(3);
a.push_back(4);
Solution s;
int result = s.search(a,target);
cout <<"The"<<" "<<target<<" "<<"is located in "<<result<<endl;
return 0;
}