Search in Rotated Sorted Array II
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.
与Find Minimum in Rotated Sorted Array,Find Minimum in Rotated Sorted Array II,Search in Rotated Sorted Array对照看
解法一：顺序查找
class Solution {
public:
bool search(int A[], int n, int target) {
for(int i = ; i < n; i ++)
{
if(A[i] == target)
return true;
}
return false;
}
};
解法二：二分查找
关键点在于，如果mid元素与low或者high元素相同，则删除一个low或者high
class Solution {
public:
bool search(int A[], int n, int target) {
int low = ;
int high = n-;
while (low <= high)
{
int mid = (low+high)/;
if(A[mid] == target)
return true;
if (A[low] < A[mid])
{
if(A[low] <= target && target < A[mid])
//binary search in sorted A[low~mid-1]
high = mid - ;
else
//subproblem from low to high
low = mid + ;
}
else if(A[mid] < A[high])
{
if(A[mid] < target && target <= A[high])
//binary search in sorted A[mid+1~high]
low = mid + ;
else
//subproblem from low to mid-1
high = mid - ;
}
else if(A[low] == A[mid])
low += ; //A[low]==A[mid] is not the target, so remove it
else if(A[mid] == A[high])
high -= ; //A[high]==A[mid] is not the target, so remove it
}
return false;
}
};