• The General Situation:
  • We commonly want to determine the interval that contains a particular value
• The Specific Situation:
  • The intervals are defined by the values in a single array
  • The intervals are disjoint
  • The union of the intervals is the set of real numbers
• Other Related Situations:
  • Conformal arrays (e.g., named left and right) that contain the left and right boundaries
  • Intervals that don't cover the reals (and, hence, the value might not be in any interval)
  • Discrete sets (e.g., of int values, of String values)

• The Boundaries:
  • \(b_0, b_1, \ldots, b_{n-1}\)
• The Intervals:
  • Interval \(0\): \([-\infty, b_0)\)
  • Interval \(1\): \([b_0, b_1)\)
  • Interval \(2\): \([b_1, b_2)\)
  • \(\vdots\)
  • Interval \(n-1\): \([b_{n-2}, b_{n-1})\)
  • Interval \(n\): \([b_{n-1}, \infty]\)

javaexamples/programmingpatterns/intervalmembership/IntervalMembership.java (Fragment: indexOf)

    /**
     * Determine which interval, defined by an array of boundaries,
     * contains a particular value. The intervals are formed from
     * the boundaries as follows:
     *
     *          Interval                     Index
     *
     * [-Infinity,      boundary[0])           0
     * [ boundary[0],   boundary[1])           1
     * [ boundary[1],   boundary[2])           2
     *                .                        .
     * [ boundary[n-2], boundary[n-1])        n-1
     * [ boundary[n-1], Infinity)              n
     *
     *
     * @param value     The value of interest
     * @param boundary  The array of boundaries that define the intervals
     * @return          The index of the interval containing the value
     */
    public static int indexOf(int value, int[] boundary) {
        int      i, n;
       
        n = Array.getLength(boundary);
       
        i = 0;
        while ((i < n) && (value >= boundary[i]))  ++i;          
       
        return i;       
    }
        

The following fragment uses interval membership to determine the tax bracket for a single individual in 2017.

javaexamples/programmingpatterns/intervalmembership/IntervalMembership.java (Fragment: taxBracket)

        int[] single = {0, 9326, 37951, 91901, 191651, 416701, 418401};

        int bracket;
        bracket = indexOf(125350, single);
        

This can be combined with a look-up array to get the marginal tax rate.

javaexamples/programmingpatterns/intervalmembership/IntervalMembership.java (Fragment: taxRate)

        double[] rate = {-1.0, 10.0, 15.0, 25.0, 28.0, 33.0, 35.0, 39.6};

        double marginal;
        marginal = rate[bracket]; 
        

• A Temptation:
  • Combine the interval membership functionality and look-up array functionality in a single method
• The Tax Example Revisited:
  • javaexamples/programmingpatterns/intervalmembership/IntervalMembership.java (Fragment: taxes)

        /**
         * Determine the U.S. (marginal) income tax rate for a single
         * person in 2017.
         *
         * @param income  The person's income
         * @return The tax rate
         */
        public static double taxRate(int income) {
            int[] single  = {0, 9326, 37951, 91901, 191651, 416701, 418401};
            double[] rate = {-1.0, 10.0, 15.0, 25.0, 28.0, 33.0, 35.0, 39.6};
    
            return rate[indexOf(income, single)];
        }    
            

• The Downside:
  • One often wants to perform more than one look-up using the same index

javaexamples/programmingpatterns/intervalmembership/IntervalMembership.java (Fragment: grades)

        int[] intervals = {
            0, 60, 63, 67, 70, 73, 77, 80, 83, 87, 90, 93};

        double[] gp = {
            -1.0, 0.0, 0.7, 1.0, 1.3, 1.7, 2.0, 2.3, 2.7, 3.0, 3.3, 3.7, 4.0};

        String[] letter = {
            "NA","F","D-","D","D+","C-","C","C+","B-","B","B+","A-","A"};

        int i;
        String out;
        
        i = indexOf(88, intervals);
        out = String.format("Grade: %s (%3.1f)", letter[i], gp[i]);