Enum InequalitySearch

  • All Implemented Interfaces:
    Serializable, Comparable<InequalitySearch>

    public enum InequalitySearch
    extends Enum<InequalitySearch>
    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
    • Enum Constant Summary

      Enum Constants 
      Enum Constant Description
      EQ
      Given a sorted array of increasing values arr[] and a key value V, this criterion instructs the binary search algorithm to find the adjacent pair of values {A,B} such that A ≤ V ≤ B.
      GE
      Given a sorted array of increasing values arr[] and a key value V, this criterion instructs the binary search algorithm to find the lowest adjacent pair of values {A,B} such that A < V ≤ B.
      Let low = index of the lowest value in the range.
      Let high = index of the highest value in the range.
      GT
      Given a sorted array of increasing values arr[] and a key value V, this criterion instructs the binary search algorithm to find the lowest adjacent pair of values {A,B} such that A ≤ V < B.
      Let low = index of the lowest value in the range.
      Let high = index of the highest value in the range.
      LE
      Given a sorted array of increasing values arr[] and a key value V, this criterion instructs the binary search algorithm to find the highest adjacent pair of values {A,B} such that A ≤ V < B.
      Let low = index of the lowest value in the range.
      Let high = index of the highest value in the range.
      LT
      Given a sorted array of increasing values arr[] and a key value v, this criterion instructs the binary search algorithm to find the highest adjacent pair of values {A,B} such that A < v ≤ B.
      Let low = index of the lowest value in the range.
      Let high = index of the highest value in the range.
    • Method Summary

      All Methods Static Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      abstract String desc​(double[] arr, int low, int high, double v, int idx)
      Optional call that describes the details of the results of the search.
      abstract String desc​(float[] arr, int low, int high, float v, int idx)
      Optional call that describes the details of the results of the search.
      abstract String desc​(long[] arr, int low, int high, double v, int idx)
      Optional call that describes the details of the results of the search.
      abstract String desc​(long[] arr, int low, int high, long v, int idx)
      Optional call that describes the details of the results of the search.
      static int find​(double[] arr, int low, int high, double v, InequalitySearch crit)
      Binary Search for the index of the double value in the given search range that satisfies the given InequalitySearch criterion.
      static int find​(float[] arr, int low, int high, float v, InequalitySearch crit)
      Binary Search for the index of the float value in the given search range that satisfies the given InequalitySearch criterion.
      static int find​(long[] arr, int low, int high, double v, InequalitySearch crit)
      Binary Search for the index of the double value in the given search range that satisfies the given InequalitySearch criterion.
      static int find​(long[] arr, int low, int high, long v, InequalitySearch crit)
      Binary Search for the index of the long value in the given search range that satisfies the given InequalitySearch criterion.
      static InequalitySearch valueOf​(String name)
      Returns the enum constant of this type with the specified name.
      static InequalitySearch[] values()
      Returns an array containing the constants of this enum type, in the order they are declared.
    • Enum Constant Detail

      • LT

        public static final InequalitySearch LT
        Given a sorted array of increasing values arr[] and a key value v, this criterion instructs the binary search algorithm to find the highest adjacent pair of values {A,B} such that A < v ≤ B.
        Let low = index of the lowest value in the range.
        Let high = index of the highest value in the range.

        If v > arr[high], return arr[high].
        If v ≤ arr[low], return -1.
        Else return index of A.

      • LE

        public static final InequalitySearch LE
        Given a sorted array of increasing values arr[] and a key value V, this criterion instructs the binary search algorithm to find the highest adjacent pair of values {A,B} such that A ≤ V < B.
        Let low = index of the lowest value in the range.
        Let high = index of the highest value in the range.

        If v ≥ arr[high], return arr[high].
        If v < arr[low], return -1.
        Else return index of A.

      • EQ

        public static final InequalitySearch EQ
        Given a sorted array of increasing values arr[] and a key value V, this criterion instructs the binary search algorithm to find the adjacent pair of values {A,B} such that A ≤ V ≤ B. The returned value from the binary search algorithm will be the index of A or B, if one of them is equal to V, or -1 if V is not equal to either one.
      • GE

        public static final InequalitySearch GE
        Given a sorted array of increasing values arr[] and a key value V, this criterion instructs the binary search algorithm to find the lowest adjacent pair of values {A,B} such that A < V ≤ B.
        Let low = index of the lowest value in the range.
        Let high = index of the highest value in the range.

        If v ≤ arr[low], return arr[low].
        If v > arr[high], return -1.
        Else return index of B.

      • GT

        public static final InequalitySearch GT
        Given a sorted array of increasing values arr[] and a key value V, this criterion instructs the binary search algorithm to find the lowest adjacent pair of values {A,B} such that A ≤ V < B.
        Let low = index of the lowest value in the range.
        Let high = index of the highest value in the range.

        If v < arr[low], return arr[low].
        If v ≥ arr[high], return -1.
        Else return index of B.

    • Method Detail

      • values

        public static InequalitySearch[] values()
        Returns an array containing the constants of this enum type, in the order they are declared. This method may be used to iterate over the constants as follows:
        for (InequalitySearch c : InequalitySearch.values())
            System.out.println(c);
        
        Returns:
        an array containing the constants of this enum type, in the order they are declared
      • valueOf

        public static InequalitySearch valueOf​(String name)
        Returns the enum constant of this type with the specified name. The string must match exactly an identifier used to declare an enum constant in this type. (Extraneous whitespace characters are not permitted.)
        Parameters:
        name - the name of the enum constant to be returned.
        Returns:
        the enum constant with the specified name
        Throws:
        IllegalArgumentException - if this enum type has no constant with the specified name
        NullPointerException - if the argument is null
      • desc

        public abstract String desc​(double[] arr,
                                    int low,
                                    int high,
                                    double v,
                                    int idx)
        Optional call that describes the details of the results of the search. Used primarily for debugging.
        Parameters:
        arr - The underlying sorted array of values
        low - the low index of the range
        high - the high index of the range
        v - the value to search for
        idx - the resolved index from the search
        Returns:
        the descriptive string.
      • desc

        public abstract String desc​(float[] arr,
                                    int low,
                                    int high,
                                    float v,
                                    int idx)
        Optional call that describes the details of the results of the search. Used primarily for debugging.
        Parameters:
        arr - The underlying sorted array of values
        low - the low index of the range
        high - the high index of the range
        v - the value to search for
        idx - the resolved index from the search
        Returns:
        the descriptive string.
      • desc

        public abstract String desc​(long[] arr,
                                    int low,
                                    int high,
                                    long v,
                                    int idx)
        Optional call that describes the details of the results of the search. Used primarily for debugging.
        Parameters:
        arr - The underlying sorted array of values
        low - the low index of the range
        high - the high index of the range
        v - the value to search for
        idx - the resolved index from the search
        Returns:
        the descriptive string.
      • desc

        public abstract String desc​(long[] arr,
                                    int low,
                                    int high,
                                    double v,
                                    int idx)
        Optional call that describes the details of the results of the search. Used primarily for debugging.
        Parameters:
        arr - The underlying sorted array of values
        low - the low index of the range
        high - the high index of the range
        v - the value to search for
        idx - the resolved index from the search
        Returns:
        the descriptive string.
      • find

        public static int find​(double[] arr,
                               int low,
                               int high,
                               double v,
                               InequalitySearch crit)
        Binary Search for the index of the double value in the given search range that satisfies the given InequalitySearch criterion. If -1 is returned there are no values in the search range that satisfy the criterion.
        Parameters:
        arr - the given array of comparable values that must be sorted with increasing values. The array must not be null and the values of the array must not be 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 NaN.
        crit - one of the InequalitySearch criteria: LT, LE, EQ, GT, GE. It must not be null.
        Returns:
        the index of the value in the given search range that satisfies the InequalitySearch criterion
      • find

        public static int find​(float[] arr,
                               int low,
                               int high,
                               float v,
                               InequalitySearch crit)
        Binary Search for the index of the float value in the given search range that satisfies the given InequalitySearch criterion. If -1 is returned there are no values in the search range that satisfy the criterion.
        Parameters:
        arr - the given array that must be sorted. It must not be null and must not contain any NaN values in the range {low, high} inclusive.
        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 NaN.
        crit - one of LT, LE, EQ, GT, GE
        Returns:
        the index of the value in the given search range that satisfies the criterion
      • find

        public static int find​(long[] arr,
                               int low,
                               int high,
                               long v,
                               InequalitySearch crit)
        Binary Search for the index of the long value in the given search range that satisfies the given InequalitySearch criterion. If -1 is returned there are no values in the search range that satisfy the criterion.
        Parameters:
        arr - the given array that must be sorted.
        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.
        crit - one of LT, LE, EQ, GT, GE
        Returns:
        the index of the value in the given search range that satisfies the criterion
      • find

        public static int find​(long[] arr,
                               int low,
                               int high,
                               double v,
                               InequalitySearch crit)
        Binary Search for the index of the double value in the given search range that satisfies the given InequalitySearch criterion. If -1 is returned there are no values in the search range that satisfy the criterion.
        Parameters:
        arr - the given array that must be sorted.
        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.
        crit - one of LT, LE, EQ, GT, GE
        Returns:
        the index of the value in the given search range that satisfies the criterion