Target must exist
Left most target
The array is like [0, 0, 0, ..., T, T, ..., T].
Following solution will return the index of the left most target satisfying isTarget(i).
public int bsearch(int n) {
int lo = 1;
int hi = n;
// only less than
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (isTarget(mid)) {
// include mid
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
Right most target
The array is like [T, T, ..., T, 0, 0, ..., 0].
Following solution will return the right most target. In this example, we are searching for the sqrt int value of an integer. we must add 1 to lo to break the tie.
public int mySqrt(int x) {
if (x == 0) {
return 0;
}
int lo = 1;
int hi = x;
int ans = 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (mid > x / mid) {
hi = mid - 1;
} else {
lo = mid + 1;
ans = mid;
}
}
return ans;
}
Target may not exist
If the target does not exist in the search range, we will return -1. In this case, we only need one answer.
public int bsearch2(int[] nums, int target) {
lo = 0;
hi = len - 1;
// less than or equal to
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
// exclude mid
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1;
}
