- Forward


Interval Membership
A Programming Pattern


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back SMYC Forward
  • 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)
Thinking About the Problem
Back SMYC Forward
  • 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]\)
The Pattern
Back SMYC Forward
javaexamples/programmingpatterns/intervalmembership/IntervalMembership.java (Fragment: indexOf)
 
An Example: U.S. Income Taxes
Back SMYC Forward

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

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

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

javaexamples/programmingpatterns/intervalmembership/IntervalMembership.java (Fragment: taxRate)
 
A Warning
Back SMYC Forward
  • 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)
       
  • The Downside:
    • One often wants to perform more than one look-up using the same index
An Example of Multiple Look-Ups: Course Grades
Back SMYC Forward
javaexamples/programmingpatterns/intervalmembership/IntervalMembership.java (Fragment: grades)
 
There's Always More to Learn
Back -