We all know binary search can be used as a way to search the occurrence index for a given value with a sorted array in O(logN) time. By simply applying some modification on a standard binary search algorithm you can achieve something more.
I. Find 1st strictly greater element in a sorted array
int bs(int arr[], int target) {
int start = 0;
int end = arr.length - 1;
int ans = -1;
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] <= target) {
start = mid + 1;
} else {
ans = mid;
end = mid - 1;
}
}
return ans;
}
II. Find 1st and last occurrence of an element (lower bound & upper bound)
public int upper_bound(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public int lower_bound(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
III. Find closest number in a sorted array
// Returns element closest to target in arr[]
int findClosest(int arr[], int n, int target)
{
if (target <= arr[0])
return arr[0];
if (target >= arr[n - 1])
return arr[n - 1];
int i = 0, j = n, mid = 0;
while (i < j) {
mid = (i + j) / 2;
if (arr[mid] == target)
return arr[mid];
if (target < arr[mid]) {
if (mid > 0 && target > arr[mid - 1])
return getClosest(arr[mid - 1], arr[mid], target);
j = mid;
} else {
if (mid < n - 1 && target < arr[mid + 1])
return getClosest(arr[mid], arr[mid + 1], target);
i = mid + 1;
}
}
return arr[mid];
}
Si Qi Cao 