Return to Answer

One method that does not incur additional memory usage is a binary search. I shall use Leonid's functions from Finding all elements within a certain range in a sorted list. With compilation and a specified starting point for the second search these would be even faster, but even without these optimizations it is still very fast.

One method that does not incur additional memory usage is a binary search. I shall use Leonid's functions from Finding all elements within a certain range in a sorted list. With compilation and a specified starting point for the second search these would be even faster, but even without these optimizations it is still very fast.

One method that does not incur additional memory usage is a binary search. I shall use Leonid's functions from Finding all elements within a certain range in a sorted list. With compilation a specified starting point for the second search these would be even faster, but even without these optimizations it is still very fast.

sorted[[5, find[5555]]] // timeAvg

One method that does not incur additional memory usage is a binary search. I shall use Leonid's functions from Finding all elements within a certain range in a sorted list. With compilation and a specified starting point for the second search these would be even faster, but even without these optimizations it is still very fast.

sorted[[5, find @ 5555]] // timeAvg

Index look-up

An extension of the second method is to create a look-up table with the IDs and indexes. This is similar to the GatherBy/GroupBy methods except that it does not require you to restructure your data into groups, merely access them in groups by index. To build the table we can use PositionIndex in 10.0.1:

asc = Span @@@ PositionIndex[First @ sorted][[All, {1, -1}]];  (* association *)

Other versions might you something like:

dsp =
  With[{sel = sorted[[1]]},
    sel[[First@#]] -> Span @@ # & /@ GatherBy[Range@Length@sel, sel[[#]] &][[All, {1, -1}]]
    ] // Dispatch;  (* Dispatch table *)

Now the extraction and timing (using the Dispatch table):

sorted[[5, 5555 /. dsp]]

{74009.2, 41782.2, 85430.2, 83496.2, 73818.2, 98949.2, 89902.2, 9615.24, 99992.2, 22660.2}

 sorted[[5, 5555 /. dsp]] // timeAvg

1.39777*10^-6

Using the Association is just a bit faster:

sorted[[5, asc @ 5555]] // timeAvg

8.7860*10^-7

The look-up table (in either format) is about 20MB:

ByteCount /@ {asc, dsp}

{19347576, 19347672}