Class Searches


  • final class Searches
    extends java.lang.Object
    Search utility methods.
    Since:
    1.1
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static int BINARY_SEARCH
      Range threshold to use a binary search.
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private Searches()
      No instances.
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) static int searchAscending​(int a, int b, double x, java.util.function.IntToDoubleFunction value)
      Conduct a search between a inclusive and b inclusive to find the highest index where value <= x.
      (package private) static int searchDescending​(int a, int b, double x, java.util.function.IntToDoubleFunction value)
      Conduct a search between a inclusive and b inclusive to find the lowest index where value <= x.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • BINARY_SEARCH

        private static final int BINARY_SEARCH
        Range threshold to use a binary search. The binary search takes O(log(n)) so is used when n is large and a sequential search is slower.
        See Also:
        Constant Field Values
    • Constructor Detail

      • Searches

        private Searches()
        No instances.
    • Method Detail

      • searchDescending

        static int searchDescending​(int a,
                                    int b,
                                    double x,
                                    java.util.function.IntToDoubleFunction value)
        Conduct a search between a inclusive and b inclusive to find the lowest index where value <= x. The values must be in descending order. The method is functionally equivalent to:
         
         i = b + 1
         while (i > a AND value(i - 1) <= x)
            i = i - 1
         return i
         

        The function is only evaluated between the closed interval [a, b]. Special cases:

        • If value(a) <= x the returned index is a.
        • If value(b) > x the returned index is b + 1.
        Parameters:
        a - Lower limit (inclusive).
        b - Upper limit (inclusive).
        x - Target value.
        value - Function to evaluate the value at an index.
        Returns:
        the minimum index where value(i) <= x.
      • searchAscending

        static int searchAscending​(int a,
                                   int b,
                                   double x,
                                   java.util.function.IntToDoubleFunction value)
        Conduct a search between a inclusive and b inclusive to find the highest index where value <= x. The values must be in ascending order. The method is functionally equivalent to:
         
         i = a - 1
         while (i < b AND value(i + 1) <= x)
            i = i + 1
         return i
         

        The function is only evaluated between the closed interval [a, b]. Special cases:

        • If value(a) > x the returned index is a - 1.
        • If value(b) <= x the returned index is b.
        Parameters:
        a - Lower limit (inclusive).
        b - Upper limit (inclusive).
        x - Target value.
        value - Function to evaluate the value at an index.
        Returns:
        the maximum index where value(i) <= x.