Most efficient way to find a range in a sequential javascript array

Question

I have an array of sequential timestamps. I need to grab the subset of the array that falls between a start and end time. A simplified example would look something like:

timestamps = [ 5,7,12,13,15,23 ];
startTime  = 6;
endTime    = 18;

Given the above example, what is the most efficient way of finding the index of the first and last timestamps that fall between the startTime and endTime?

A correct script would discover and return indexes 1 & 4 (timestamps[1], timestamps[4])

I could loop through the array and do a comparison, but is there a more efficient way?

EDIT :: My solution - Binary search :

(Coffeescript)

 # Search ordered array for timestamps falling between 'start' & 'end'
 getRangeBorderIndexes = (stack, start, end) ->
  ar    = []
  ar[0] = getBorder( stack, start, "left" )
  ar[1] = getBorder( stack, end, "right"  )
  return ar

# Use bisection (binary search) to find leftmost or rightmost border indexes
getBorder = (stack, value, side ) ->
  mod1       = if side == "left"  then 0 else -1 
  mod2       = if side == "left"  then 1 else  0

  startIndex = 0
  stopIndex  = stack.length - 1
  middle     = Math.floor( (stopIndex+startIndex)/2 )

  while stack[middle] != value && startIndex < stopIndex
    if value < stack[middle]
      if value > stack[middle - 1] then return middle + mod1
      stopIndex = middle - 1

    else if value > stack[middle]
      if value < stack[middle + 1] then return middle + mod2
      startIndex = middle + 1

    middle = Math.floor( (stopIndex+startIndex)/2 )

  return if stack[middle] != value then -1 else middle

timestamps = [ 5,7,12,13,15,23 ]
startTime  = 6
endTime    = 18

getRangeBorderIndexes( timestamps, startTime, endTime) # returns [1,5]

@kennebec and @Shanimal gave great responses, especially if you are wanting a super simple method for grabbing a subset of an array. However I needed indexes of the sub array rather than the entire sub array. I did some testing, and the above example consistently takes about 7ms to find the borders of the sub array, even on an array with 10 million entries!

Thanks to @voithos for pointing me in the right direction. I also modified this code to create the solution above.

If your array is large, you could use a modification of the bisection method. — voithos
– voithos, Commented Mar 4, 2013 at 16:58
If you can guarantee that the array is always sorted, then it's one simple for loop, not really worth worrying about efficiency unless it's a bottleneck. — zzzzBov
– zzzzBov, Commented Mar 4, 2013 at 16:58
Just loop throught, and test for the absolute value of the difference between current timestamps value and startTime or endTime. — JoDev
– JoDev, Commented Mar 4, 2013 at 17:03
@voithos This is super helpful, I wasn't aware of the bisection/binary search pattern. I'm playing around with this example, seems promising. — tolmark
– tolmark, Commented Mar 4, 2013 at 17:14

Shanimal · Accepted Answer · 2013-03-04 17:02:51Z

2

Using the lodash / underscore library:

_.select(timestamps,function(i){
    return i>=startTime && i<=endTime;
})

answered Mar 4, 2013 at 17:02

Shanimal

11.8k7 gold badges67 silver badges82 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

tolmark Over a year ago

very cool, knew about underscore, but hadn't seen lodash. Thanks!

Shanimal Over a year ago

thanks for dropping a note. lodash is an always thoughtful, well maintained, fine tuned drop in replacement for underscore. it's faster too! lodash.com/benchmarks. cheers!

tolmark Over a year ago

After playing with lodash, it's very efficient, thanks again!

kennebec · Accepted Answer · 2013-03-04 17:11:08Z

Looping is efficient, but Array.filter is easier-

var timestamps = [ 5,7,12,13,15,23 ],

startTime  = 6,
endTime    = 18;


var selected=timestamps.filter(function(itm){
return itm>=startTime   && itm<=endTime;
});

/* returned value: (Array) 7,12,13,15 */

// filter is built into most browsers, but if you need to support IE before #9 you can shim it:

if(!Array.prototype.filter){
    Array.prototype.filter= function(fun, scope){
        var T= this, A= [], i= 0, itm, L= T.length;
        if(typeof fun== 'function'){
            while(i<L){
                if(i in T){
                    itm= T[i];
                    if(fun.call(scope, itm, i, T)) A[A.length]= itm;
                }
                ++i;
            }
        }
        return A;
    }
}

Collectives™ on Stack Overflow

Most efficient way to find a range in a sequential javascript array

EDIT :: My solution - Binary search :

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

EDIT :: My solution - Binary search :

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related