# Efficient way of picking a subset that fulfills criteria

## Main Question or Discussion Point

Let's say there is a set of n elements, S. P is a subset of S, with m elements, and satisfies some conditions, i.e. c1 < f(P) < c2 and g(P) < c3, where f and g are some functions on the elements of P and c1, c2 and c3 are constants.

For practical purposes, S is represented as a sorted array of n floating point numbers.

The objective is to find which elements satisfy the above conditions.

My current approach is rather brute force, i.e. exhaustively trying out combinations. I'm wondering whether there is some more efficient way.

Related Programming and Computer Science News on Phys.org
.Scott
Homework Helper
In the general case of any f and g, no.

But, for example, if f and g are monotonic, then yes.
In that case:
-- find d1, d2, and d3 for f(d1)=c1; f(d2)=c2; and g(d3)=c3.
-- rewrite the selection criteria in terms of d1, d2, and d3: d1<P<d2 or d1>P>d2 and d3>P or d3<P.
-- if possible, combine those ranges. For example if d1<P<d2; P>d3; and d1<d3; then only d3<P<d2 is needed.
-- do a binary search in S for the d1, d2, and d3 values that remain boundary values.