Searching for items in a JSON object using binary search

Question

Searching for items in a JSON object using binary search

My JSON object contains data organized like this:

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

The time* values represent dates in milliseconds and are sorted in sequence.

Now, I need to search for an item based on the time key. If the key doesn't exist, I must find the nearest value. There are thousands of entries in the object and I'm considering using binary search, but I'm unsure about how to implement it.

The traditional method of calculating the middle position middle = (right+left)/2 cannot be used because the middle value might be undefined. Due to the fixed structure of my data, I am unable to utilize a binary tree.

Any insights or suggestions would be greatly appreciated.

javascript json

Answer 1

Answer №1

If the median is undefined, a simple approach would be to take the middle key by dividing the length of the json by 2. Although not ideal, it gets the job done. Following this, a binary search can be conducted while keeping track of the index at each step. The goal is to check for indexes and determine whether to move left or right based on the value at each index. In case you reach a dead end and the searched time does not exist, you still have an idea of the surrounding values. For this, a final check using the formula if ((time_to_search - json[index-1]) > (json[index+1] - time_to_search)) can help decide which element is closer - index-1 or index+1. This operation is O(1) so there's no need to worry. You can then return either json[index-1] or json[index+1].

Does this explanation make sense to you?

I've also included a Fiddle for reference: http://jsfiddle.net/QFTJ5/

Please note that the Fiddle provided is not complete.

Answer 2

If the median is undefined, a simple approach would be to take the middle key by dividing the length of the json by 2. Although not ideal, it gets the job done. Following this, a binary search can be conducted while keeping track of the index at each step. The goal is to check for indexes and determine whether to move left or right based on the value at each index. In case you reach a dead end and the searched time does not exist, you still have an idea of the surrounding values. For this, a final check using the formula if ((time_to_search - json[index-1]) > (json[index+1] - time_to_search)) can help decide which element is closer - index-1 or index+1. This operation is O(1) so there's no need to worry. You can then return either json[index-1] or json[index+1].

Does this explanation make sense to you?

I've also included a Fiddle for reference: http://jsfiddle.net/QFTJ5/

Please note that the Fiddle provided is not complete.

Answer 3

Answer №2

If you want to extract only the suffixes with a time label from an array, here's how:

let data = {
  "time1": {
    "item1": "value1",
    "item2": "value2"
  },
  "time2": {
    "item1": "value3",
    "item2": "value4"
  }
}
let postfixes = [];
for (let key in data) {
  postfixes.push(key.substring(4));
}

You can then perform a binary search on the extracted postfixes.

Answer 4

If you want to extract only the suffixes with a time label from an array, here's how:

let data = {
  "time1": {
    "item1": "value1",
    "item2": "value2"
  },
  "time2": {
    "item1": "value3",
    "item2": "value4"
  }
}
let postfixes = [];
for (let key in data) {
  postfixes.push(key.substring(4));
}

You can then perform a binary search on the extracted postfixes.

Answer 5

Answer №3

Given the scenario

var schedule = {
  "1367999303810": { 
    "task1": "value1",
    "task2": "value2"
  },
  "1368000000000": { 
    "task1": "value3",
    "task2": "value4"
  }
}

A potential coding solution could look like this (Math corrections needed!)

Live Example

function findClosestTime(targetTime) {
  for (var i=0; i<scheduledTimes.length; i++) {
    window.console && console.log(new Date(targetTime), new Date(scheduledTimes[i]))      
    if (targetTime === scheduledTimes[i]) return targetTime;  
    if (targetTime >= scheduledTimes[i]) break;
  }
  if (i == scheduledTimes.length) return -1; 
  if (i == scheduledTimes.length-1) return scheduledTimes[i];  
  var diff1 = Math.abs(targetTime - scheduledTimes[i]),     
  diff2 = Math.abs(scheduledTimes[i+1] - targetTime);   
   return diff1 === diff2 ? scheduledTimes[i+1] : 
          diff2 > diff1 ? scheduledTimes[i] : scheduledTimes[i+1]; 
}    

var scheduledTimes = [];

for (var t in schedule) scheduledTimes.push(parseInt(t));
scheduledTimes.sort();
var targetTime = new Date(2013,4,8,9,50,0).getTime(); 
var closestTime = findClosestTime(targetTime); 
if (closestTime != -1) window.console && console.log(schedule[closestTime])

Answer 6

Given the scenario

var schedule = {
  "1367999303810": { 
    "task1": "value1",
    "task2": "value2"
  },
  "1368000000000": { 
    "task1": "value3",
    "task2": "value4"
  }
}

A potential coding solution could look like this (Math corrections needed!)

Live Example

function findClosestTime(targetTime) {
  for (var i=0; i<scheduledTimes.length; i++) {
    window.console && console.log(new Date(targetTime), new Date(scheduledTimes[i]))      
    if (targetTime === scheduledTimes[i]) return targetTime;  
    if (targetTime >= scheduledTimes[i]) break;
  }
  if (i == scheduledTimes.length) return -1; 
  if (i == scheduledTimes.length-1) return scheduledTimes[i];  
  var diff1 = Math.abs(targetTime - scheduledTimes[i]),     
  diff2 = Math.abs(scheduledTimes[i+1] - targetTime);   
   return diff1 === diff2 ? scheduledTimes[i+1] : 
          diff2 > diff1 ? scheduledTimes[i] : scheduledTimes[i+1]; 
}    

var scheduledTimes = [];

for (var t in schedule) scheduledTimes.push(parseInt(t));
scheduledTimes.sort();
var targetTime = new Date(2013,4,8,9,50,0).getTime(); 
var closestTime = findClosestTime(targetTime); 
if (closestTime != -1) window.console && console.log(schedule[closestTime])

Searching for items in a JSON object using binary search

Answer №1

Answer №2

Answer №3

Similar questions

What is the best way to retrieve the initial element from a map containing certain data?

Utilize a single JavaScript script to handle numerous HTML forms within the same webpage

While attempting to use JavaScript and AJAX to read a JSON object, I encountered an issue caused by the CORS

When switching tabs in Javascript, the page does not automatically reload. However, the page will reload only when it is on

Code malfunctioning

Display or conceal elements by utilizing ng-show/ng-hide according to specific conditions

Utilizing Astro Project to gather content from various directories containing Markdown files

"Is there a way to verify the existence of checkbox array values within a database using PHP Laravel

Access to Web Share API requires permission

Exploring the Functionality of ngMousedown and ngMouseup in AngularJS

Tips for showcasing chats with the most recent message highlighted

Static file serving is malfunctioning

The error message in AuthenticatedLayout.jsx on line 43 indicates a problem with trying to access properties of an undefined object, specifically the 'name'

Items outside the container element

Shifting v-slot references into a Vue.js component - tips and tricks!

Instructions for transferring numerous chosen files (such as .doc, .pdf, .jpeg, .png) to a server from an Android device

The order in which JavaScript is being executed is being reversed

Troubleshooting problem with populating data in Mongoose Database

Unlimited scrolling with external JSON data in AngularJS

The schema tag contains incorrect JSON syntax