称号
Follow up for "Search 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.
解题思路
这题和Search in Rotated Sorted Array问题类似。只是这个题同意元素反复。假设有元素反复，此时採取最保守的策略。一次缩小一个范围。
代码实现
class Solution {
public:
bool search(int A[], int n, int target) {
if(A==NULL || n<=0) return false;
int begin = 0, end = n-1, mid = 0;
while(begin<=end){
mid = (begin+end)/2;
if(A[mid] == target) return true;
if(A[mid] < A[end]){
//后半段有序
if(A[end]>=target && A[mid]<target)
begin = mid+1;
else
end = mid - 1;
}else if(A[mid] > A[end]){
//前半段有序
if(A[begin]<=target && A[mid] > target)
end = mid-1;
else
begin = mid+1;
}else
// 最保守策略，缩小一个范围
--end;
}
return false;
}
};
假设你认为本篇对你有收获。请帮顶。
另外。我开通了微信公众号--分享技术之美，我会不定期的分享一些我学习的东西.
你能够搜索公众号：swalge 或者扫描下方二维码关注我
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvc3dhZ2xl/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="">
（转载文章请注明出处: http://blog.csdn.net/swagle/article/details/30487759
)
)
版权声明：本文博主原创文章。博客，未经同意不得转载。