Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
47 lines (42 sloc) 1.18 KB
problem:
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.
----------------------------------------------------------------
solution:
//当有重复的元素时,比如数组{1, 0, 1, 1, 1}和{1, 1, 1, 0, 1}这两个数组中,第一个数字、最后一个数字和中间一个数字都是1,
//我们无法确定中间的数字1属于第一个递增子数组还是属于第二个递增子数组。这个时候只能用顺序查找
bool search(int A[], int n, int target)
{
if(n <= 0)
return false;
int l = 0;
int r = n-1;
while(l <= r)
{
int mid = (l + r) / 2;
if(A[mid] == target)
return true;
//都与A[r]进行比较,若出现相等,则r--(类似进行顺序查找)
if(A[mid] > A[r]) //左部分有序
{
if(A[l] <= target && target < A[mid]) //target在左部分
r = mid - 1;
else
l = mid + 1;
}
else if(A[mid] < A[r])//右部分有序
{
if(A[r] >= target && target > A[mid]) //target在右部分
l = mid + 1;
else
r = mid - 1;
}
else
{
r--;
}
}
return false;
}