Follow up for LeetCode - 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.
Just when A[left]==A[center], we cannot say the previous part is ordered, then we just go to the next element and check again.
Just when A[left]==A[center], we cannot say the previous part is ordered, then we just go to the next element and check again.
public boolean search(int[] A, int target) {
if (A == null || A.length == 0)
return false;
int left = 0, right = A.length - 1;
// Apply binary search when it is sure which part is sorted
while (left <= right) {
int center = (left+right) / 2;
if (A[center] == target) // Target found
return true;
if (A[center] > A[left]) { // The left part is sorted
if (target >= A[left] && target < A[center])
right = center - 1;
else
left = center + 1;
} else if (A[center] < A[left]) { // The right part is sorted
if (target <= A[right] && target > A[center])
left = center + 1;
else
right = center - 1;
} else { // cannot say which part is sorted
left++;
}
}
return false;
}
Read full article from LeetCode - Search in Rotated Sorted Array II | Darren's Blog
No comments:
Post a Comment