Most efficient way to find a range in a sequential javascript array
<p>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:</p>

<pre><code>timestamps = [ 5,7,12,13,15,23 ];
startTime  = 6;
endTime    = 18;
</code></pre>

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

<p>A correct script would discover and return indexes 1 &amp; 4 (<code>timestamps[1], timestamps[4]</code>)</p>

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

<hr>

<h2><strong>EDIT :: My solution - Binary search :</strong></h2>

<p><strong>(Coffeescript)</strong></p>

<pre><code> # Search ordered array for timestamps falling between 'start' &amp; 'end'
 getRangeBorderIndexes = (stack, start, end) -&gt;
  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 ) -&gt;
  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 &amp;&amp; startIndex &lt; stopIndex
    if value &lt; stack[middle]
      if value &gt; stack[middle - 1] then return middle + mod1
      stopIndex = middle - 1

    else if value &gt; stack[middle]
      if value &lt; 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]
</code></pre>

<p>@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!</p>

<p>Thanks to @voithos for pointing me in the right direction. I also modified <a href="http://www.nczonline.net/blog/2009/09/01/computer-science-in-javascript-binary-search/" rel="nofollow">this code</a> to create the solution above.</p>
