net.sf.kdgcommons.collections

Class BinarySearch

java.lang.Object

net.sf.kdgcommons.collections.BinarySearch

public class BinarySearch
extends Object

A collection of static methods for searching array-like data structures: those that can be accessed using an integer index. Examples of such structures include a java.nio.LongBuffer, or a file consisting of fixed-size records.

There are two ways to search these structures. For structures that are sorted, you can implement BinarySearch.Accessor: the search will provide that interface with indexes to compare. Or, you can create an int[] that holds sorted indexes into the original data structure, and implement BinarySearch.IndexedComparator: the search will provide the comparator with indexes retrieved from that array.

In either case, you must implement a compare() method that compares an actual object instance against the instance stored at a particular index in your data structure.

As with Arrays.binarySearch(), each of these methods returns the index if successful, (-(insertionPoint) - 1) if not. The specific meaning of insertionPoint will vary depending on the method called; see the method docs for details.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	BinarySearch.Accessor<T> Implement this interface if you're searching an already-sorted array-like structure.
static interface	BinarySearch.IndexedComparator<T> Implement this interface if you have an int[] that contains sorted indexes into the array-like structure.

Constructor Summary

Constructors

Constructor and Description
BinarySearch()

Method Summary

Modifier and Type	Method and Description
static <T> int	search(BinarySearch.Accessor<T> accessor, T value) Searches a sorted array-like structure using the provided Accessor.
static <T> int	search(int[] index, T value, BinarySearch.IndexedComparator<T> cmp) Searches sorted array of indexes into some other array-like object (which does not need to be sorted).

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 static <T> int search(BinarySearch.Accessor<T> accessor,
                             T value)

Searches a sorted array-like structure using the provided Accessor. If the object is found, the returned value will be the object's location within that structure.

If the object is not found, the value of the returned insertion point will depend on the accessor's defined range. If the accessor's range covers the entire structure, or if the object would appear within the defined range, then the returned insertion point will indicate the position where the object should be inserted. If the accessor covers a subset of the structure, and the missing object would appear outside that structure, then the insertion point will be just before or just after the defined range, not the absolute position in the array.

This is best illustrated with examples. Given the array ['B', 'D', 'F', 'H', 'J', 'L', 'N', 'P', 'R']:

• A search for the value 'C', covering the entire range, would return -2. This is the same behavior as the JDK's built-in searches.
• A search for the value 'C', covering elements 2..4, would return -3. This is because the search doesn't know of any values outside the range, so it would indicate that the value should be inserted just before the range.
• A search for the value 'B', covering the elements 2..4, would also return -3. Although 'B' appears in the complete array, it is not in the search range. And, like 'C', the search only knows that it should be inserted before the range.
• A search for the value 'F', covering the elements 2..4, could return +2.
• A search for the value 'G', covering the elements 2..4, would return -4. This insertion point is within the range being searched, so is accurate.
• A search for the value 'J', covering the elements 2..4, would return -5. This is because, although the value of element 4 is 'J', the upper bound of the range is exclusive. So the search can't find the value, and reports that it would be inserted after the range.
• A search for the value 'L', covering the elements 2..4, would also return -5, indicating that the value could not be found within the bounds of the search (even though it exists outside those bounds).

search

public static <T> int search(int[] index,
                             T value,
                             BinarySearch.IndexedComparator<T> cmp)

Searches sorted array of indexes into some other array-like object (which does not need to be sorted). Returns the position/insertion point of the requested value within the index array.