JSON对象中的二进制搜索 [英] Binary search in JSON object

问题描述

我有一个像这样的JSON对象:

I have a JSON object like this:

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

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

The value of time* is the new Date() value in milliseconds, so the sequence of the time* value is sorted.

现在我必须在时间之前搜索一个项目，如果该键不存在，则必须取最接近的值. 我在该对象中有成千上万的条目，我在考虑二进制搜索，但是我不知道该怎么做.

Now I have to search an item by time, if the key doesn't exist I have to take the nearest value. I have thousands of entries in the object and I'm thinking about the binary search but I have no idea about how to do.

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

I can't use the classic way middle = (right+left)/2 because the middle value could be undefined. I can't use binary tree because I have a defined structure I can't change.

谢谢

推荐答案

问题是您可能没有为中位数定义，但是以最简单的形式，您只能使用中间键json.length/2，这并不是最佳选择但它有效. 接下来，您必须进行二进制搜索，但还要保留每一步的位置索引. 本质上，您要检查的是索引，并确定是否要根据每个索引的值向右或向左移动. 如果您走到了尽头，则搜索的时间不存在，您确实知道邻居"，最后检查，if ((time_to_search - json[index-1]) > json[index+1] - time_to_search))来检查与[c7>或index+1之间的距离是否更近(这是O(1)所以你很好)，最终您可以返回json[index-1]或json[index+1].

The problem is that you can have undefined for the median, but at the simplest form you can just take the middle key, json.length/2, it is not optimal but it works. Next you'd have to do the binary search but also keep the index of where you are at each step. Essentially what you are checking is for indexes and decide if to move right or left by the value at each index. If you hit a dead end, the searched time doesn't exist, you do know the "neighbourhood", last check, if ((time_to_search - json[index-1]) > json[index+1] - time_to_search)) to check where is it closer, to index-1 or index+1 (This is O(1) so you're good) and eventually you can return either json[index-1] or json[index+1].

这对您有意义吗?

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

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

这篇关于JSON对象中的二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！