Only One situation need to be done.
When A[L] == A[mid].
public boolean search(int[] A, int target) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int L = 0;
int R = A.length-1;
while (L<=R) {
int mid = (L+R)/2;
if (A[mid] == target) return true;
// Example: 4 5 6 7 8 9 1 2 3
if (A[L] < A[mid]) {
if (A[L]<=target && target < A[mid]) {
R = mid - 1;
} else {
L = mid + 1;
}
}
// Example: 8 9 1 2 3 4 5 6 7
else if (A[L] > A[mid]) {
if (A[mid] < target && target <= A[R]) {
L = mid + 1;
} else {
R = mid - 1;
}
} else {
L++;
}
}
return false;
}
No comments:
Post a Comment