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

Question

Searching by closest and position 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.)

Answer 1

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

Answer 2

In versions 10+, you can have a NearestFunction that returns multiple properties, such as the "Index" of the nearest element and the "Element" itself:

SeedRandom[42];
haystack = RandomReal[1, 1000000];
f = Nearest[haystack ->{"Index", "Element"}];

AbsoluteTiming[f[.312345]]

{0.000072, {{101999, 0.312345}}}