Top Description Inners Constructors Methods
io.smallrye.common.search

public final Class BinarySearch

extends Object
Class Inheritance
Imports
java.util.Comparator, .List, .Objects, java.util.function.BiFunction, .BiPredicate, .BinaryOperator, .IntBinaryOperator, .IntPredicate, .LongBinaryOperator, .LongPredicate, .Predicate, io.smallrye.common.function.ObjIntFunction, .ObjIntPredicate, .ObjLongFunction, .ObjLongPredicate
A utility class which provides multiple variations on binary searching.

Ranges

The binary search algorithm operates over a range of values. The search will always return in logarithmic time with respect to the search interval. This implementation supports multiple kinds of value ranges: Each of these methods returns an object with find() methods that perform variations on the binary search.

Range predicates

Ranges are searched by predicate. The predicate is evaluated for the lowest value within the range (that is, the value closest to the from argument) for which it returns true. If no value satisfies the predicate, the highest value (that is, the value given for the to argument) is returned. The value returned by each find() method is always within the range [from, to].

In order to be well-defined, the predicate must be continuous, which is to say that given some value n, the predicate must return false for all < n and true for all >= n when from ≤ n ≤ to. If this constraint does not hold, then the results of the search will not be well-defined. The behavior of the predicate outside of this range does not affect the well-definedness of the search operation.

Inverted ranges

It is possible to search over an inverted range, i.e. a range for which to is numerically lower than from. While such searches are well-defined, it should be noted that the from bound remains inclusive while the to bound remains exclusive, which might be surprising in some circumstances.

Nested and Inner Type Summary

Modifier and TypeClass and Description
private static interface
BinarySearch.IntIdxTestFunction<A, B, C, D>

public static class
BinarySearch.IntRange

Search operations which apply over an int range.

private static interface
BinarySearch.LongIdxTestFunction<A, B, C, D>

public static class
BinarySearch.LongRange

Search operations which apply over an long range.

private static interface
BinarySearch.ObjIdxTestFunction<T, A, B, C, D>

public static class
BinarySearch.ObjRange

Binary searches over a range of objects.

Constructor Summary

AccessConstructor and Description
private
BinarySearch()

Method Summary

Modifier and TypeMethod and Description
public static <
the array element type
E> E

Returns:

the array value at the index
getFromArray(E[]
the array (must not be null)
array, int
the array index
index)

A getter function which can satisfy ObjIntFunction<E[], E> for accessing values in an array.

public static BinarySearch.IntRange

Returns:

an object which can perform binary searches over an integer range (not null)
intRange()

Returns an object which can perform binary searches over an integer range (not null).

public static BinarySearch.LongRange

Returns:

an object which can perform binary searches over a long integer range (not null)
longRange()

Returns an object which can perform binary searches over a long integer range (not null).

public static BinarySearch.ObjRange

Returns:

an object which can perform binary searches over an object range (not null)
objRange()

Returns an object which can perform binary searches over an object range (not null).

private static <A, B, C, D> int
searchInt(int from, int to, A a, B b, C c, D d, IntBinaryOperator midpoint, BinarySearch.IntIdxTestFunction<A, B, C, D> test)

private static <A, B, C, D> long
searchLong(long from, long to, A a, B b, C c, D d, LongBinaryOperator midpoint, BinarySearch.LongIdxTestFunction<A, B, C, D> test)

private static <T, A, B, C, D> T
searchObject(T from, T to, A a, B b, C c, D d, BinaryOperator<T> midpoint, BinarySearch.ObjIdxTestFunction<T, A, B, C, D> test)

private static int
signedMidpoint(int from, int to)

private static long
signedMidpoint(long from, long to)

private static int
unsignedMidpoint(int from, int to)

private static long
unsignedMidpoint(long from, long to)

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait