Find index on ranged values using Javascript

Question

Given the following ranges and indexes:

index   from        to
11      24          48
10      12          24
9       6           12
8       3           6
7       1.5         3
6       0.75        1.5
5       0.375       0.75
4       0.1875      0.375
3       0.09375     0.1875
2       0.046875    0.09375
1       0.0234375   0.046875
0       0.015625    0.0234375

How should I organize this (data/algorithm) to have something similar to:

x=0.22;
n=findIndex(x);
alert(n);

// output 4

Obviously it may work for any size of indexes. The only thing in my mind goes about nested ifs...

thx.

How did you get each of those ranges? They appear to be 24/(2^k) for increasing values of k, except for that last from entry, which would be 0.01171875. — beaker
– beaker, Commented Apr 16, 2014 at 16:55
Can you elaborate how x=0.22 returns 4? As in what is the calculation. ? — Ashima
– Ashima, Commented Apr 16, 2014 at 16:56
@Beaker I think from = to/2. He is just doubling the values and commas are actually decimals — Ashima
– Ashima, Commented Apr 16, 2014 at 16:57
@Ishita That's basically what I said, but my point was that 0.015625 != 0.0234375/2. If this was just a mistake then we can get the index using lg(n/24) or somesuch. — beaker
– beaker, Commented Apr 16, 2014 at 17:06
@beaker indeed it should be something like 24/(2^(11-k)) but the answer must be more generic to be useful for other types of (regular or not) ranges. — Paulo Bueno
– Paulo Bueno, Commented Apr 16, 2014 at 17:11

TriniBoy · Accepted Answer · 2014-04-16 17:11:06Z

4

I would write something like this:

var indexes = {
  11 : [24, 48], 
  10 : [12, 24],
  9 : [6, 12],
  8 : [3, 6],
  7 : [1.5, 3],
  6 : [0.75, 1.5],
  5 : [0.375, 0.75],
  4 : [0.1875, 0.375],
  3 : [0.09375, 0.1875],
  2 : [0.046875, 0.09375],
  1 : [0.0234375, 0.046875],
  0 : [0.015625, 0.0234375]
};

var x = 0.22;
var n = findIndex(x);

function findIndex(d){
    for(var key in indexes){
    if(d >= indexes[key][0] && d <= indexes[key][1]) 
      return key;
     }
}
alert(n);

Fiddle

May not be the most efficient code, happy for improvements.

edited Apr 16, 2014 at 17:11

answered Apr 16, 2014 at 17:05

TriniBoy

6903 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Vikram Bhat · Accepted Answer · 2014-04-16 16:56:23Z

2

Use binary Search on the index range using and check if the point is within or either side of the range of given index.

answered Apr 16, 2014 at 16:56

Vikram Bhat

6,3063 gold badges22 silver badges19 bronze badges

2 Comments

Paulo Bueno Over a year ago

binary Search may be faster and more adaptable then the answer accepted, but the theme is too extensive. thx anyway.

Vikram Bhat Over a year ago

@PauloBueno you are right it is a overkill for your requirement but can use if needed in future

Patrick · Accepted Answer · 2014-04-16 17:22:01Z

Since it looks like the array is sorted, why don't you use binary search algorithm. I put together a jsfiddle using binary search and match criteria assumes inclusive "from". In other words 6 would match 9 and not 8.

ranges = [
    {from: .015625, to: .0234375},
    {from: .0234375, to: .046875},
    {from: .046875, to: .09375},
    {from: .09375, to: .1875},
    {from: .1875, to: .375},
    {from: .375, to: .75},
    {from: .75, to: 1.5},
    {from: 1.5, to: 3},
    {from: 3, to: 6},
    {from: 6, to: 12},
    {from: 12, to: 24},
    {from: 24, to: 48}
];


//A function that can build an array of ranges
//by doubling the seed... This looks to produce a
//different results than your ranges as 
// .0234375 is not twice .015625.
var buildRanges = function (seed, maxIndex) {
    var tmp = [];
    var curr = 0;
    var from = seed;
    var to = 2 * from;
    while (curr <= maxIndex) {
        tmp.push({from: from, to: to});
        from = to;
        to = 2 * from;
        curr++;
    }

    return tmp;
}

var findIndex = function (x) {
    var min = 0;
    var max = ranges.length - 1
    var mid;
    while (min <= max) {
        mid = parseInt((max + min) / 2);
        //Assume "from" field is inclusive
        if (x >= ranges[mid].from && x < ranges[mid].to) {
            return mid;
        }
        //We know that maximum must be adjusted below mid
        else if (x < ranges[mid].from) {
            max = mid - 1;
        }
        //Else we must move up the min
        else {
            min = mid + 1;
        }
    }
}

alert(findIndex(.22)); //4
alert(findIndex(6)); //9
alert(findIndex(12)); //10
alert(findIndex(.9)); //6

Collectives™ on Stack Overflow

Find index on ranged values using Javascript

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related