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.
我的思路：
太混乱了 不提了。注意关键区分依据 排好序的一定是从小到大的
看大神的吧：
bool search(int A[], int n, int key) {
int l = , r = n - ;
while (l <= r) {
int m = l + (r - l)/;
if (A[m] == key) return true; //return m in Search in Rotated Array I
if (A[l] < A[m]) { //left half is sorted 排好序的部分一定是从小到大的
if (A[l] <= key && key < A[m]) //在排好序的这部分
r = m - ;
else
l = m + ;
} else if (A[l] > A[m]) { //right half is sorted
if (A[m] < key && key <= A[r])
l = m + ;
else
r = m - ;
} else l++; //A[l] == A[m] 把l增大1个再循环
}
return false;
}
我的代码，把三个数字都相等的情况单独处理，其他就用无重复处理。 其实我的代码看起来长一些，但是在处理1111111111115这种情况时我的方法优势还是有的
bool search(int A[], int n, int target) {
int l = , r = n - ;
while(l <= r)
{
int m = (l + r) / ;
if(target == A[m])
return true;
else if(A[l] == A[m] && A[m] == A[r]) //三个值相等
{
bool isequalleft = true;
for(int i = l; i < m; i++)
{
if(A[i] != A[i + ])
{
isequalleft = false;
break;
}
}
if(isequalleft) //去掉重复的那一半
l = m + ;
else
r = m - ;
}
else //与不重复的方法相同
{
if (A[l] <= A[m]) {
if (target >= A[l] && target < A[m]) {
r = m - ;
} else {
l = m + ;
}
} else {
if (target > A[m] && target <= A[r]) {
l = m + ;
} else {
r = m - ;
}
}
}
}
return false;
}