Getting the value from key in a dictionary that is nearest to a given number using JavaScript

Question

I have a dictionary (keys are integers, values are float). I would now ask the dictionary for the value of the key that is > than the given number but < than the next greater key.

Example:

dict = {100: 0.0035, 150: 0.0024, 200: 0.0019}.

i give 122, it should give me 0.0035

i give 333, it should give me 0.0019

i give 200, it should give me 0.0024

Thanks!

Answer 1

This is a perfect use-case for a binary tree. The topic is a little broad for a stack overflow answer, but here goes anyway.

function addValueToNode(tree, nodeidx, value) {
    var left = 2*nodeidx + 1;
    var right = 2*nodeidx + 2;

    if(value > tree[nodeidx]) {
        if(!tree[right])
            tree[right] = value;
        else
            addValueToNode(tree, right, value);
    } else {
        if(!tree[left])
            tree[left] = value;
        else
            addValueToNode(tree, left, value);
    }
}

function addValueToTree(tree, value) {
    if(tree.length == 0)
        tree.push(value)
    else
        addValueToNode(tree, 0, value);
}

function addValuesToTree(tree, values) {
    for(var i = 0; i < values.length; i++)
        addValueToTree(tree, values[i]);
}

function addDictionaryToTree(tree, dict) {
    var values = [];
    for(var key in dict) {
        values.push(key);
    }
    values.sort();
    addValuesToTree(tree, values);
}

function findClosestValue(tree, nodeidx, value) {
    var left = 2*nodeidx + 1;
    var right = 2*nodeidx + 2;

    if(value > tree[nodeidx]) {
        if(!tree[right] || tree[right] == value)
            return tree[nodeidx];
        else
            return findClosestValue(tree, right, value);
    } else {
        if(!tree[left])
            return tree[nodeidx];
        else
            return findClosestValue(tree, left, value);
    }
}
var tree = [];
var dict = {100: 0.0035, 150: 0.0024, 200: 0.0019};

addDictionaryToTree(tree, dict);

var closest = findClosestValue(tree, 0, 175);
var dictValue = dict[closest];

alert( closest + " : " + dictValue);