com.partnersoft.data

Class BinarySearch

java.lang.Object

com.partnersoft.data.BinarySearch

All Implemented Interfaces:

SearchingAlgorithm

public class BinarySearch
extends java.lang.Object
implements SearchingAlgorithm

A generic binary search algorithm.

This search method requires that keys be presorted in order; however it is very fast and reliable.

This isn't declared as a singleton, since it has no actual overhead (no state), so there's not strong reason to limit instantiation. However an standardInstance() method is provided that provides a shared instance.

You can also just use this via the handy convenience method SearchingLib.binarySearch(SearchingGopher, Object); that is actually the recommended method.

Copyright 2000-2006 Partner Software, Inc.

Author:

Paul Reavis

Constructor Summary

Constructors

Constructor and Description
BinarySearch() Creates a new BinarySearch algorithm object.

Method Summary

Methods

Modifier and Type	Method and Description
int	findClosest(SearchingGopher gopher, java.lang.Object key) Finds the slot where the given key would go if it were in there.
int	findClosest(SearchingGopher gopher, java.lang.Object key, int start, int end) Finds the slot where the given key would go if it were in there over the given inclusive range (start <= i <= end).
int	search(SearchingGopher gopher, java.lang.Object key) Searches for the given key using the given gopher.
int	search(SearchingGopher gopher, java.lang.Object key, int start, int end) Searches for the given key using the given gopher over the given range (start <= i < end).
static BinarySearch	standardInstance() Returns a singleton shared instance.

Methods inherited from class java.lang.Object

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

Constructor Detail

BinarySearch

public BinarySearch()

Creates a new BinarySearch algorithm object. Generally you don't need to do this; this constructor is provided to allow serialization and instantiation, but you can almost always just use the standardInstance() method.

Method Detail

standardInstance

public static BinarySearch standardInstance()

Returns a singleton shared instance.

Returns:

standard BinarySearch instance

search

public int search(SearchingGopher gopher,
         java.lang.Object key)

Description copied from interface: SearchingAlgorithm

Searches for the given key using the given gopher. Returns -1 if the search fails.

Specified by:

search in interface SearchingAlgorithm

Parameters:

gopher - adapter to underlying array-like structure

key - value to search for

Returns:

index of found item, or -1 if search failed

search

public int search(SearchingGopher gopher,
         java.lang.Object key,
         int start,
         int end)

Description copied from interface: SearchingAlgorithm

Searches for the given key using the given gopher over the given range (start <= i < end). Returns -1 if the search fails.

Specified by:

search in interface SearchingAlgorithm

Parameters:

gopher - adapter to underlying array-like structure

key - value to search for

start - start of index range, inclusive (start <= i)

end - end of index range, exclusive (i < end)

Returns:

index of found item, or -1 if search failed

findClosest

public int findClosest(SearchingGopher gopher,
              java.lang.Object key)

Description copied from interface: SearchingAlgorithm

Finds the slot where the given key would go if it were in there. Always returns something. Useful for insertion-based structures, or for near-match searches.

Specified by:

findClosest in interface SearchingAlgorithm

Parameters:

gopher - adapter to underlying array-like structure

key - value to search for

Returns:

index of found item, or index where found item would be inserted if it were there

findClosest

public int findClosest(SearchingGopher gopher,
              java.lang.Object key,
              int start,
              int end)

Description copied from interface: SearchingAlgorithm

Finds the slot where the given key would go if it were in there over the given inclusive range (start <= i <= end). Always returns something. Useful for insertion-based structures, or for near-match searches.

Specified by:

findClosest in interface SearchingAlgorithm

Parameters:

gopher - adapter to underlying array-like structure

key - value to search for

start - start of index range, inclusive (start <= i)

end - end of index range, exclusive (i < end)

Returns:

index of found item, or index where found item would be inserted if it were there