Binary search in JSON object

Question

I have a JSON object like this:

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

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.

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.

Thanks

read values into array? (indexed by `timevalue - firstTimeValue`) — Andrey Sidorov, May 08 '13 at 07:35
can you give an actual example with the "value of time*" - a JSFiddle.net would be great — mplungjan, May 08 '13 at 07:38
Keep in mind that the order of properties in an object is [not guaranteed](http://stackoverflow.com/questions/5525795/does-javascript-guarantee-object-property-order), so you'd have to convert it to an array before you could do a meaningful binary search. From there, it's pretty straightforward. — Dagg Nabbit, May 08 '13 at 07:49
The `time*` values are something like 1368000928818. For example, some consecutive values are 1368000928818, 1368000938821, 1368000948821 and 1368000958824. You can see that there isn't a common difference between values. — Max Markson, May 08 '13 at 08:16
"nearest value", or "matching or next lowest value"? The latter is somewhat easier... — Alnitak, May 08 '13 at 08:22

gmaliar · Accepted Answer · 2013-05-08T08:13:03.283

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].

Does that makes sense to you?

Added a fiddle, http://jsfiddle.net/QFTJ5/

Note: this is not a complete fiddle

This has sense but json.length returns `undefined` – Max Markson May 08 '13 at 08:13 — Max Markson, May 08 '13 at 08:13
Right, you'd have to use this `Object.keys(json).length` – gmaliar May 08 '13 at 08:19 — gmaliar, May 08 '13 at 08:19

score 1 · Answer 2 · answered May 08 '13 at 07:42

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.

answered May 08 '13 at 07:42

Boris Strandjev

46,145
15
108
135

Copy all items is useless...at this point I can run through all elements and search directly the item I'm looking for, but this will be time consuming (as copying the array) – Max Markson May 08 '13 at 08:15
@MaxMarkson I don't copy all items - just construct array of the numbers you are interested in. I am not sure whether it will have performance impact (in fact I have godfeeling that as this is a lot simpler data structure the search will be faster). On the other hand the code will surely become easier to understand with my suggestion. After all it is you call, though – Boris Strandjev May 08 '13 at 08:24

score 1 · Answer 3 · edited Jan 29 '14 at 22:59

Assuming

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

I would code something like this (Please fix the math!)

Live Demo

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])

Binary search in JSON object

3 Answers3

Linked