Module io.smallrye.common.search

Package io.smallrye.common.search

Class BinarySearch

java.lang.Object

io.smallrye.common.search.BinarySearch

public final class BinarySearch
extends Object

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:

• int via the intRange() method
• long via the longRange() method
• Object ranges via the objRange() method

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 Class Summary

Nested Classes

Modifier and Type	Class	Description
static final class	BinarySearch.IntRange	Search operations which apply over an int range.
static final class	BinarySearch.LongRange	Search operations which apply over an long range.
static final class	BinarySearch.ObjRange	Binary searches over a range of objects.

Method Summary

Modifier and Type	Method	Description
static <E> E	getFromArray(E[] array, int index)	A getter function which can satisfy ObjIntFunction<E[], E> for accessing values in an array.
static BinarySearch.IntRange	intRange()	Returns an object which can perform binary searches over an integer range (not null).
static BinarySearch.LongRange	longRange()	Returns an object which can perform binary searches over a long integer range (not null).
static BinarySearch.ObjRange	objRange()	Returns an object which can perform binary searches over an object range (not null).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

intRange

public static BinarySearch.IntRange intRange()

Returns an object which can perform binary searches over an integer range (not null). The returned object operates on a signed range by default.

Returns:

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

See Also:

• BinarySearch.IntRange.unsigned()

longRange

public static BinarySearch.LongRange longRange()

Returns an object which can perform binary searches over a long integer range (not null). The returned object operates on a signed range by default.

Returns:

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

See Also:

• BinarySearch.LongRange.unsigned()

objRange

public static BinarySearch.ObjRange objRange()

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

Returns:

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

getFromArray

public static <E> E getFromArray(E[] array,
 int index)

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

Type Parameters:

E - the array element type

Parameters:

array - the array (must not be null)

index - the array index

Returns:

the array value at the index