这是我的基本的问题：我给一个 currentTime的。例如，750个秒。我也有，其中包含1000-2000对象，每个对象都有一个的startTime ， endTime的，以及一个数组 _id 属性。鉴于 currentTime的，我需要找到具有的startTime 和 endTime的落在该范围内的 - 例如，的startTime：740 ，结束时间：755 。

  VAR arrayLength = array.length;
变种X = 0;
而（X＆LT; arrayLength）{
 如果（currentTime的＆GT; =阵列[X] .startTime和放大器;＆安培; currentTime的＆LT; =阵列[X] .endTime）{
  //然后我发现我的对象
 }
X ++;
};
 

编辑：为了清楚起见， currentTime的有下跌的的startTime 和 endTime的

我的解决办法：我的数据的结构得到了我一定的好处，可以让我把事情简单化了一点。我做了一个基本的二进制搜索，如建议，因为该数组已按startTime时。我还没有完全测试这个东西的速度，但我怀疑这是一个公平的有点快，尤其是对于较大的阵列。

  VAR的binarySearch =功能（阵列，currentTime的）{

  VAR低= 0;
  VAR高= array.length  -  1;
  变种我;

  而（低＆LT; =高）{
    I = Math.floor（（低+高）/ 2）;

    如果（数组[我] .startTime＆LT; = currentTime的）{

      如果（数组[我] .endTime＆GT; = currentTime的）{
        //这是一个
        返回数组[我] ._ ID;

      } 其他 {
        低= I + 1;
      }
    }

    其他 {
      高= I  -  1;
    }
  }

  返回null;
}
 

解决方案

要解决这个问题，最好的方法取决于多少次，你将不得不打电话给你的搜索功能。

如果您调用函数只是几次，假设 M 时间，去为线性搜索。这个函数的调用的总体复杂性将是 O（MN）。

如果您调用你的函数多次，然后通过的许多的我的意思是超过的log（n）倍你应该：

平均情况： O（nlogn）的初始化和 O（LOGN）对于每个搜索

最坏的情况：包含许多相等的部分，或者说有一个共同的区间段，并寻找在此区间的数组。在这种情况下，你会做 O（nlogn）的初始化和 O（N + LOGN）= O（N）搜索。

Here's my basic problem: I'm given a currentTime. For example, 750 seconds. I also have an array which contains 1000 to 2000 objects, each of which have a startTime, endTime, and an _id attribute. Given the currentTime, I need to find the object that has a startTime and endTime that falls within that range -- for example, startTime : 740, endTime : 755.

What is the most efficient way to do this in Javascript?

I've simply been doing something like this, for starters:

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++;
};

But I suspect that looping isn't the best option here. Any suggestions?

EDIT: For clarity, the currentTime has to fall within the startTime and endTime

My solution: The structure of my data affords me certain benefits that allows me to simplify things a bit. I've done a basic binary search, as suggested, since the array is already sorted by startTime. I haven't fully tested the speed of this thing, but I suspect it's a fair bit faster, especially with larger arrays.

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;
}

The best way to tackle this problem depends on the number of times you will have to call your search function.

If you call your function just a few times, let's say m times, go for linear search. The overall complexity for the calls of this function will be O(mn).

If you call your function many times, and by many I mean more than log(n) times, you should:

Average case: O(nlogn) for initialization and O(logn) for each search.

Worst case: an array containing many equal segments, or segments that have a common interval, and searching in this interval. In that case you will do O(nlogn) for initialization and O(n + logn) = O(n) for search.