有效地找到落在一定数量范围内的物体

Question

这是我的基本问题:我得到了一个currentTime.例如,750秒.我也有其含有1000〜2000的对象,其每一个有一个的阵列startTime,endTime和一个_id属性.鉴于此currentTime,我需要找到具有a startTime且endTime属于该范围的对象 - 例如startTime : 740,endTime : 755.

在Javascript中执行此操作的最有效方法是什么？

对于初学者来说,我只是做了这样的事情:

var arrayLength = array.length; 
var x = 0;
while (x < arrayLength) {
 if (currentTime >= array[x].startTime && currentTime <= array[x].endTime) {
  // then I've found my object
 }
x++;
};

但我怀疑循环不是这里的最佳选择.有什么建议？

编辑:为了清楚起见,currentTime必须落在startTime和endTime

我的解决方案:我的数据结构为我提供了一些好处,使我能够简化一些事情.我已按照建议完成了基本二进制搜索,因为数组已经按startTime排序.我还没有完全测试过这个东西的速度,但我怀疑它的速度要快一些,特别是对于更大的阵列.

var binarySearch = function(array, currentTime) {

  var low = 0;
  var high = array.length - 1;
  var i; 

  while (low <= high) {
    i = Math.floor((low + high) / 2);

    if (array[i].startTime <= currentTime) {

      if (array[i].endTime >= currentTime ){
        // this is the one
        return array[i]._id; 

      } else {
        low = i + 1;
      }
    }

    else {
      high = i - 1;
    }
  } 

  return null;
}

Answer 1

解决此问题的最佳方法取决于您必须调用搜索功能的次数.

如果你只调用几次你的功能,那就说m时间,去线性搜索.调用此函数的总体复杂性将是O(mn).

如果你打电话给你的功能很多次,和很多我的意思是超过log(n)时候,你应该:

• 排序数组中O(nlogn)通过startTime,然后通过endTime如果你有几个项目具有相等值startTime
• 进行二进制搜索以查找元素范围startTime <= x.这意味着进行两次二进制搜索:一次用于start范围,一次用于end范围.这是完成的O(logn)
• 在里面做线性搜索[start, end].你必须做线性搜索,因为顺序startTimes告诉你什么都没有endTimes.这可以是O(1)和之间的任何地方O(n),它取决于细分的分布和值x.

平均情况: O(nlogn)用于初始化和O(logn)每次搜索.

最坏情况:包含许多相等段的数组,或具有公共间隔的段,并在此间隔中搜索.在这种情况下,您将O(nlogn)进行初始化和O(n + logn) = O(n)搜索.