# Efficiently searching a list for the position of the closest number to a specified number

Searching by and I wasn't able to find an answer—but found Nearest by guessing. Nearest, however, returns the closest number itself, not the position.

After some more looking around, I learned about MapIndexed and Rules, and came up with this:

NearestPosition[haystack_, needle_] := Nearest[haystack, needle] /. MapIndexed[Rule, haystack];


Is there a more efficient way, in general?

(And what if it's guaranteed the list comes sorted—can that be leveraged?)

The reason I'm concerned about efficiency is that I intend to use NearestPosition in a DynamicModule where it may be triggered by every mouseover event. (I'm still trying to solve this problem.)

-
thinking about it computationally, you'd need to check every number to determine which one is the closest number. So best you got is O(n). If it's sorted, you obviously can do a lot better by binary search and such. Anyway, what happens if there are multiple instances of the closest number? Do you expect it to take the closest or last? – Jonie Oct 23 '13 at 5:00
@Jonie - Currently my implementation (above) returns what Nearest would return by default: a list of all "tied" for the closest. (I don't need any of Nearest's other features, like closest-within-a-radius, closest-n, etc.) – Andrew Cheong Oct 23 '13 at 5:02

SeedRandom[42];
haystack = RandomReal[1, 6300];
AbsoluteTiming[
f = Nearest[haystack -> Range@Length@haystack];
{f[.3, 1], haystack[[f[.3, 1]]]}]

(*

-> {0.015625, {{3123}, {0.300033}}}

*)


Of course in this case most of the time is expended calculating the nearest function. If your points aren't changing from one use to the next, the time for calculating f[}is nil for 6K points.

The second argument of f[] specifies that Nearest[] should return only one point

-
You could use Automatic instead of Range. – Sjoerd C. de Vries Oct 23 '13 at 6:45
Thanks for the cleaner solution. And indeed, I may be prematurely optimizing. – Andrew Cheong Oct 23 '13 at 11:14
@SjoerdC.deVries Yep, used it here mathematica.stackexchange.com/a/34620/193 – Dr. belisarius Oct 23 '13 at 15:13
Thanks, I didn't know that I can precalculate something like NearestFunction. :) – Kuba Oct 24 '13 at 7:18