Fastest Way To Compare A Number To A List Of Numbers In A Range?

Is there a method faster in performance than doing this: var value = 2432; if (value >= 20 && value <= 31) return true; else if (value >= 45 && value <

Solution 1:

So if ranges are unique and don't intersect with each other. The fastest way to check I see to be next algo:

1. make a list of pairs [start, end] or just use two separated lists for start points and end points.
2. sort them(it could be done really easy on SQL side)
3. using binary search find out first start value that is larger than your reference number
4. previous item give your just single range you should check against your reference number.

If sorting is done on DB side, then this algo will be O(logN) that is fast enough.

Solution 2:

You could make an array of [start, end] arrays:

const ranges = [
    [20, 31],
    [45, 47],
    [82, 86],
    // …
    [1052, 1065],
    [2400, 2500]
  ];

Then use Array.prototype.find or Array.prototype.some to find a range that a value is in (e.g. let value = 2432;):

ranges.find(([start, end]) => value >= start && value <= end); // Returns `[2400, 2500]`, which is the range the value is in, or
!!ranges.find(([start, end]) => value >= start && value <= end); // Returns `true`, since the value is in a range, or
ranges.some(([start, end]) => value >= start && value <= end); // Returns `true`, since the value is in a range, or

Solution 3:

You can certainly reduce the number of conditional statements you have to write.

Assuming your "from-to" arrays arrive from the server in the form [ [n1, n2], [n3, n4], ... ], you can loop over each of your ranges and return from the function once you have a match, or return false otherwise:

let ranges = [ [20, 31], [45, 47] ];
let valueInRange = 46;
let valueNotInRange = 33;

function isValInRange(value, rangeArr) {
    for(let i = 0; i < rangeArr.length; i++) {
        if(value >= rangeArr[0] && value <= rangeArr[1]) {
            return true;
    }
    return false;
}

console.log(isValInRange(valueInRange, ranges)); //true
console.log(isValInRange(valueNotInRange, ranges)); //false

Solution 4:

If you can do the query in sql and there is no intersection, then just have a table with all possible values between 1 and 65000 and have a bool column if the number is valid with indices. You only really take a hit on an update performance wise. In this case do:

Value isRange
1     true

SELECT * FROM RangeTable where Value = @Value and isRange = true

This optimizes for reading, however if you update frequently then this will not help.

Are you updating frequently?

Solution 5:

If you're going to be checking against these values significantly more than you'll update them, one option would be to construct a tree with the ranges and search it a little faster than iterating through all of the options. You will want to keep the tree balanced, though, or it won't do you much good.

/*
  Construct this dynamically
  min: range minimum
  max: range maximum
  lt: node for ranges less than this range
  gt: node for ranges greater than this range
  I'd probably make a class for this.
*/
const ranges = {
  min: 82,
  max: 86,
  lt: {
    min: 45,
    max: 47,
    lt: {
      min: 20,
      max: 31
    }
  },
  gt: {
    min: 2400,
    max: 2500,
    lt: {
      min: 1052,
      max: 1065
    }
  }
};

function lookup(value) {
  let current = ranges;
  while (current) {
    if (value < current.min) {
      current = current.lt;
    } else if (value > current.max) {
      current = current.gt;
    } else {
      return true;
    }
  }
  return false;
}

This essentially does this for the value:

1. Go to middle range.
2. If current node is null, return false (value not in any range).
3. If value is in current range, return true (value is in range).
4. If value is less than current min, go to middle range less than current and go back to step 2.
5. If value is greater than current max, go to middle range greater than current and go back to step 2.