Hi there,

I have a little problem and would like to hear some opinions about it:

Well let's consider the simplest way of my problem:
given is a set of Points in an interval (starting with 0) - let P be the Number of these points.
And given is a partitioning of that interval in M partitions - for example an array whose entries are the (sorted) endpoints of the partitions.

My problem is to find an efficient way to compute for every point in P the number of the partition in which he lies.

(i haven't decided yet if the points are given by a list or an array)

really tricky is : the number of M and P may vary in scale
P and M can be really small but also VERY large

my options are :
-binary search for each point on the partitioning
or
-sort the points and then
( -one-sided-binary search on the partitioning
or
-interpolation search on the partitioning )

Do anyone see any other option?

And now the main problem :
Is there is best all-over-choice for all possible numbers P and M ?
if not : when would pay each option above?

(for little M and large P binary search would do best, i think, but what does "little" mean in dependence to P ?)

I know my English sucks but i hope someone is able to understand my problem.

thx in return for answers !
greetz