Get the next and previous element of an array given an index

Question

Given I have an array in Javascript, with values as such;

0     => 0x0000FF
1200  => 0x00CCFF
28800 => 0xFF0AFF
36000 => 0xFFFFFF

How can I determine which elements a given index value falls between? With the previous example, if I have the value 31073, I need to retrieve 28800 => 0xFF0AFF and 36000 => 0xFFFFFF

Answer 1

There's no "built-in" way to accomplish this with Javascript's sparse arrays. The simplest way to do this for arbitrary sparse indexes while maintaining some efficiency is to keep another lookaside sorted array of the indexes into the main array. Then you can walk the lookaside list to find the right neighbor indexes, and go back to the main array to get their values.

If your array will be huge or accesses need to be faster than O(items), you could look into various tree structures for the lookaside object.

Answer 2

Here's one way that simply uses a couple while() loops with no body.

It assumes the starting point will always be in between. You'll need a couple of quick additional tests if that's not the case.

Also, I wasn't sure what should happen if the starting point is directly on a color, so I didn't account for that.

Example: http://jsfiddle.net/tcVxP/4/

var num = 31234,
    curr = num,
    prev,
    next;

while( !colors[--curr] && curr );
prev = colors[curr];

curr = num;
while( !colors[++curr] );
next = colors[curr];