Search in Rotated Sorted Array II
Search in Rotated Sorted Array II
青木
发布于 2018-10-09 15:59:36
发布于 2018-10-09 15:59:36
文章被收录于专栏：我是业余自学C/C++的
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.
允许数组旋转，并且还允许数组重复，这种情况下，还是可以使用二分法来查找目标元素。
如果允许数组中元素重复，在数组旋转之后，am>=a1的情况下，1~m之间的数组就不一定是单调递增的。比如{1，3，1，1，1}. 其实只有等于号的情况下，递增性是不确定的。那就需要将=和>分开考虑。
- am>a1，则在1,m之间，数组一定是递增的，就算有重复元素，这一段也还是递增的。
- am=a1，在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;
} (adsbygoogle = window.adsbygoogle || []).push({}); function googleAdJSAtOnload() { var element = document.createElement("script"); element.src = "//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"; element.async = true; document.body.appendChild(element); } if (window.addEventListener) { window.addEventListener("load", googleAdJSAtOnload, false); } else if (window.attachEvent) { window.attachEvent("onload", googleAdJSAtOnload); } else { window.onload = googleAdJSAtOnload; }本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
