# Class GenericInequalitySearch

java.lang.Object
org.apache.datasketches.quantilescommon.GenericInequalitySearch

public final class GenericInequalitySearch extends Object
This provides efficient, unique and unambiguous binary searching for inequality comparison criteria for ordered arrays of values that may include duplicate values. The inequality criteria include <, ≤, ==, ≥, >. All the inequality criteria use the same search algorithm. (Although == is not an inequality, it is included for convenience.)

In order to make the searching unique and unambiguous, we modified the traditional binary search algorithm to search for adjacent pairs of values {A, B} in the values array instead of just a single value, where a and b are the array indices of two adjacent values in the array. For all the search criteria, when the algorithm has narrowed the search down to a single value or adjacent pair of values, the resolve() method provides the final result of the search. If there is no valid value in the array that satisfies the search criterion, the algorithm will return -1 to the caller.

Given a sorted array of values arr[] and a search key value v, the algorithms for the searching criteria are given with each enum criterion.

Author:
  Lee Rhodes
See Also:
  - Sketching Quantiles and Ranks Tutorial

## Nested Class Summary

Nested Classes
Modifier and Type
Class
Description
`static enum`
`GenericInequalitySearch.Inequality`
The enumerator of inequalities

## Constructor Summary

Constructors
Constructor
Description
`GenericInequalitySearch()`
No argument constructor.

## Method Summary

Modifier and Type
Method
Description
`static <T> int`
`find(T[] arr, int low, int high, T v, GenericInequalitySearch.Inequality crit, Comparator<T> comparator)`
Binary Search for the index of the generic value in the given search range that satisfies the given Inequality criterion.

### Methods inherited from class Object

`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

## Constructor Details

### GenericInequalitySearch

public GenericInequalitySearch()
No argument constructor.

## Method Details

### find

public static <T> int find(T[] arr, int low, int high, T v, GenericInequalitySearch.Inequality crit, Comparator<T> comparator)
Binary Search for the index of the generic value in the given search range that satisfies the given Inequality criterion. If -1 is returned there are no values in the search range that satisfy the inequality.

Type Parameters:
  `T` - The generic type of value to be used in the search process.
Parameters:
  `arr` - the given array of comparable values that must be sorted. The array must not be null or empty and the values of the array must not be null (or NaN) in the range [low, high].
  `low` - the lowest index of the lowest value in the search range, inclusive.
  `high` - the highest index of the highest value in the search range, inclusive.
  `v` - the value to search for. It must not be null (or NaN).
  `crit` - one of the Inequality criteria: LT, LE, EQ, GE, GT. It must not be null.
  `comparator` - for the type T. It must not be null. It must return: -1 if A < B, 0 if A == B, and +1 if A > B.
Returns:
  the index of the value in the given search range that satisfies the Inequality criterion.