javascript - 在顺序 javascript 数组中查找范围的最有效方法

Question

我有一组顺序时间戳。我需要获取介于开始时间和结束时间之间的数组子集。一个简化的例子看起来像:

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

在上面的示例中，找到位于 startTime 和 endTime 之间的第一个和最后一个时间戳的索引的最有效方法是什么？

正确的脚本会发现并返回索引 1 和 4 (timestamps[1], timestamps[4])

我可以遍历数组并进行比较，但有没有更有效的方法？

---

编辑::我的解决方案 - 二进制搜索:

( 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 和@Shanimal 给出了很好的回应，特别是如果你想要一个 super 简单的方法来获取数组的一个子集。但是我需要子数组的索引而不是整个子数组。我做了一些测试，上面的示例始终需要大约 7 毫秒才能找到子数组的边界，即使是在具有 1000 万个条目的数组上也是如此!

感谢@voithos 为我指明了正确的方向。我也修改了this code创建上面的解决方案。

Answer 1

使用 lodash/underscore 库:

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