Java实现 lower_bound() 和 upper_bound()
lower_bound()
函数 lower_bound() 在 [begin, end) 进行二分查找，返回 大于或等于 tar的第一个元素位置。如果所有元素都小于tar，则返回 end.
public class LowerBound {
public static int lower_bound(int[] arr, int begin, int end, int tar) {
while(begin < end) {
int mid = begin + (end - begin) / 2;
// 当 mid 的元素小于 tar 时
if(arr[mid] < tar)
// begin 为 mid + 1, arr[begin] 的值会小于或等于 tar
begin = mid + 1;
// 当 mid 的元素大于等于 tar 时
else if(arr[mid] >= tar)
end = mid;
}
return begin;
}
}
upper_bound()
函数 upper_bound() 在 [begin, end) 进行二分查找，返回 大于 tar的第一个元素位置。如果所有元素都小于tar，则返回 end.
public class UpperBound {
public static int upper_bound(int[] arr, int begin, int end, int tar) {
while(begin < end) {
int mid = begin + (end - begin) / 2;
if(arr[mid] <= tar)
begin = mid + 1;
else if(arr[mid] < tar)
end = mid;
}
return begin;
}
}
参考链接
[sumy的博客](http://sumygg.com/2017/09/08/upper-bound-and-lower-bound-in-java/)