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
-sort the points and then
( -one-sided-binary search on the partitioning
-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 !