  Given a weighted, ordered query set $Q$ and a partition of $Q$ into classes,
we study the problem of computing a minimum-cost decision tree that, given any
query $q$ in $Q$, uses equality tests and less-than comparisons to determine
the class to which $q$ belongs. Such a tree can be much smaller than a lookup
table, and much faster and smaller than a conventional search tree. We give the
first polynomial-time algorithm for the problem. The algorithm extends
naturally to the setting where each query has multiple allowed classes.
