org.lenskit.util

Class BinarySearch

java.lang.Object

org.lenskit.util.BinarySearch

public abstract class BinarySearch
extends java.lang.Object

Utility class for implementing and working with binary searches. Binary searches over arbitrary structures can be performed by subclassing this class. Instances must capture the target (the key to be searched for), there is not a means of providing the key at search time.

Constructor Summary

Constructors

Constructor and Description
BinarySearch()

Method Summary

Modifier and Type	Method and Description
static <E extends java.lang.Comparable<? super E>> BinarySearch	forList(E needle, java.util.List<? extends E> haystack) Create a search over a list.
static int	resultToIndex(int res) Convert a possibly-negative binary search result to an index or insertion point.
int	search(int start, int end) Perform a binary search across a range of integers.
protected abstract int	test(int pos) Test the value at position pos, comparing it against the target.

Methods inherited from class java.lang.Object

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

Constructor Detail

BinarySearch

public BinarySearch()

Method Detail

search

public int search(int start,
                  int end)

Perform a binary search across a range of integers. This is much like Arrays.binarySearch(Object[], Object), but allows for searching over arbitrary indexed structures, and has defined behavior when the input sequence contains repeated elements (it always finds the first).

The efficiency guarantees of this method assume that there are not very many objects equal to the target element, as it does a linear scan to find the first once it finds one.

Parameters:

start - The lower bound of the binary search (inclusive). Must be nonnegative.

end - The upper bound of the binary search (exclusive). Must be no less than start.

Returns:

The position in the range [start,end) where the target is found. If the target is not found, then the value \(-i-1\) is returned, where \(i\) is the insertion point, the point at which the target would be inserted to appear in sorted order (the index of the first entry greater than the target, or end if the target is greater than all members). If multiple items match the target, this method is guaranteed to return the index of the first (unlike Arrays.binarySearch(Object[], Object)).

Throws:

java.lang.IllegalArgumentException - if start or end is out of range.

test

protected abstract int test(int pos)

Test the value at position pos, comparing it against the target. p To understand this method, suppose that an array objs of Comparable objects is being searched. Then calling this method is equivalent to:

target.compareTo(objs[pos])

Returns:

A negative value if the target is less than the value at position pos, positive if it is greater, and 0 if the objects should be considered equal.

forList

public static <E extends java.lang.Comparable<? super E>> BinarySearch forList(@Nonnull
                                                                               E needle,
                                                                               @Nonnull
                                                                               java.util.List<? extends E> haystack)

Create a search over a list.

Parameters:

needle - The item to search for.

haystack - The list to search

E - The element type.

Returns:

A binary search that, when searched, will search for needle in haystack.

resultToIndex

public static int resultToIndex(int res)

Convert a possibly-negative binary search result to an index or insertion point.

Parameters:

res - The result

Returns:

The index (if res is nonnegative) or insertion point (if it is negative).