I receive a list of real numbers ( float ) between $0$ and $1$.  The list has length $N+1$ and I need to find two numbers on the list which are $\le \frac{1}{N}$ apart.  Here is an example test case:[ 0.        ,  0.31662479,  0.63324958,  0.94987437,  0.26649916,  0.58312395,  0.89974874,  0.21637353,  0.53299832,  0.84962311,  0.1662479 ,  0.48287269,  0.79949748,  0.11612227,  0.43274706,  0.74937186,  0.06599665]One possibility I came up with is to multiply by $N=17$ and to take the integer part:[ 0,  5, 10, 16,  4,  9, 15,  3,  9, 14,  2,  8, 13,  1,  7, 12,  1]Then I have to find the location of two numbers in this list which are identical.I would appreciate any solution to this problem with or without the intermediate multiplication step.  Or does this problem have a particular name in the field of algorithms?
Find the duplicates in a list of floating point numbers
sorting;integers;floating point;lists
SortingThe simplest algorithm is to sort your floats, then compare adjacent entries.  This will let you find all pairs that are $\le \frac1N$ apart in $O(N \lg N)$ time.HashingIt's also possible to come up with a linear-time algorithm, i.e., to check whether there is any nearby pair of floats and if so find at least, in $O(N)$ time.Let $M=\lfloor N/2 \rfloor$.  Build a list of integers by replacing each float $x$ with $\lfloor Mx \rfloor$, then find all duplicates in the resulting list of integers.  Finding duplicates in a list of integers can be done in expected linear time by hashing and looking for a pair with the same hash.  For each duplicate integer, check whether it corresponds to a pair of floats that differ by $\le \frac1N$.Then, do it again: build a second list of integers by replacing each float $x$ with $\lfloor Mx + 0.5 \rfloor$, then find all duplicates in this list and check each to see whether it corresponds to a pair of floats that differ by $\le \frac1N$.It's possible to show that if there exists a pair of floats that differ by $\le \frac1N$, then this procedure will find at least one such pair; and if there aren't any such pair, then this procedure will discover that fact.  Moreover, with suitable choice of the hash function, this can be made to run in expected linear time.  In fact, if you replace the hashing with counting sort, this runs in deterministic linear time.In practiceIn practice, my advice is to simply sort and then compare adjacent entries.  It will be easier to implement, less fiddly (you don't have to deal with corner cases), obviously correct, and probably more than fast enough in practice.