Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
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:O(logn)
public class Solution {
public boolean search(int[] A, int target) {
if(A == null || A.length == 0)
return false;
return doSearch(0,A.length-1,A,target);
}
public boolean doSearch(int start, int end, int[] A, int target){
if(end< start || (end == start && A[start]!=target ))
return false;
int m = (start+end)/2;
if(A[m] == target)
return true;
if(A[m] < A[start]){
if(A[m] <= target && target <=A[end])
return doSearch(m+1,end,A,target);
else
return doSearch(start,m-1,A,target);
}
else if(A[m] > A[start]){
if(A[m] >= target && target >=A[start])
return doSearch(start,m-1,A,target);
else
return doSearch(m+1,end,A,target);
}
else if(A[m] == A[start]){
if(A[m] != A[end])
return doSearch(m+1,end,A,target);
else
return doSearch(start,m-1,A,target) || doSearch(m+1,end,A,target);
}
return false;
}
}
Key Concept:always do binary search in correct session.
沒有留言:
張貼留言