Package org.elasticsearch.common.util

Class BinarySearcher

java.lang.Object
org.elasticsearch.common.util.BinarySearcher
Direct Known Subclasses:
BigArrays.DoubleBinarySearcher
public abstract class BinarySearcher extends Object
Performs binary search on an arbitrary data structure. To do a search, create a subclass and implement custom compare(int) and distance(int) methods. BinarySearcher knows nothing about the value being searched for or the underlying data structure. These things should be determined by the subclass in its overridden methods. Refer to BigArrays.DoubleBinarySearcher for an example. NOTE: this class is not thread safe

  • Constructor Details

    • BinarySearcher

      public BinarySearcher()

  • Method Details

    • compare

      protected abstract int compare(int index)
      Returns:
      a negative integer, zero, or a positive integer if the array's value at index is less than, equal to, or greater than the value being searched for.

    • distance

      protected abstract double distance(int index)
      Returns:
      the magnitude of the distance between the element at index and the value being searched for. It will usually be Math.abs(array[index] - searchValue).

    • search

      public int search(int from, int to)
      Uses a binary search to determine the index of the element within the index range {from, ... , to} that is closest to the search value. Unlike most binary search implementations, the value being searched for is not an argument to search method. Rather, this value should be stored by the subclass along with the underlying array.
      Returns:
      the index of the closest element. Requires: The underlying array should be sorted.