Suppose you have an unsorted array of numeric values and need to find the set of indexes of all the values which are within a range. The range predicate will be evaluated many times, so any time spent preprocessing will be amortised, and non-zero spatial overhead is expected. If the data were sorted, this would be very easy, but the indexes of the values have meaning so the data cannot be sorted. To complicate the problem slightly, the set of indexes must be produced in sorted order.
