2

我有一个这样的 JSON 对象：

"time1": {
    "item1": "val1",
    "item2": "val2"
},
"time2": {
    "item1": "val3",
    "item2": "val4"
}
...

的值time*是以new Date()毫秒为单位的值，因此对time*值的顺序进行了排序。

现在我必须按时间搜索一个项目，如果键不存在，我必须取最接近的值。我在对象中有数千个条目，我正在考虑二进制搜索，但我不知道该怎么做。

我不能使用经典方式middle = (right+left)/2，因为中间值可能是undefined. 我不能使用二叉树，因为我有一个无法更改的已定义结构。

谢谢

4

3 回答 3

2

问题是你可以有未定义的中位数，但在最简单的形式下，你可以只取中间键，json.length/2它不是最优的，但它可以工作。接下来，您必须进行二进制搜索，但还要保留您在每一步中所在位置的索引。本质上，您要检查的是索引，并根据每个索引处的值决定是向右还是向左移动。如果您遇到死胡同，搜索时间不存在，您确实知道“邻居”，最后一次检查，if ((time_to_search - json[index-1]) > json[index+1] - time_to_search))检查它在哪里更接近index-1或index+1（这O(1)很好），最终您可以返回json[index-1]或json[index+1]。

这对你有意义吗？

添加了一个小提琴，http://jsfiddle.net/QFTJ5/

注意：这不是一个完整的小提琴

于 2013-05-08T07:55:25.257 回答
1

Here is how you read only the time suffixes in an array:

var json = {
  "time1": {
    "item1": "val1",
    "item2": "val2"
  },
  "time2": {
    "item1": "val3",
    "item2": "val4"
  }
}
var values = [];
for (var i in json) {
  values += i.substring(4);
}

Now you can do binary search on the values indices.

于 2013-05-08T07:42:16.620 回答
1

假设

var times = {
  "1367999303810": { // today at 9:48am
    "item1": "val1",
    "item2": "val2"
  },
  "1368000000000": { // today at 10am
    "item1": "val3",
    "item2": "val4"
  }
}

我会编写这样的代码（请修正数学！）

现场演示

function getNearest(findTime) {
  for (var i=0;i<tArr.length;i++) {
    window.console && console.log(new Date(findTime),new Date(tArr[i]))      
    if (findTime === tArr[i]) return findTime;  // exact match
    if (findTime >= tArr[i]) break; // pinpoint
  }
  if (i==tArr.length) return -1; // nothing found
  if (i==tArr.length-1) return tArr[i];  // found the end
  // here the time to find is greater than one of the array entries
  var diff1 = Math.abs (findTime - tArr[i]),     // distance from last entry
  diff2 = Math.abs (tArr[i+1] - findTime);   // distance to next entry
   return diff1 === diff2 ? tArr[i+1] : // return the newest time
          diff2 > diff1 ? tArr[i] : tArr[i+1]; //  or the nearest
}    



var tArr = [];

for (var t in times) tArr.push(parseInt(t));
tArr.sort();
var findTime = new Date(2013,4,8,9,50,0).getTime(); // today at 9:50
var time = getNearest(findTime); 
if (time !=-1) window.console && console.log(times[time])
于 2013-05-08T08:14:43.837 回答