Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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 <= 47) return true;
else if (value >= 82 && value <= 86) return true;
...
else if (value >= 1052 && value <= 1065) return true;
else if (value >= 2400 && value <= 2500) return true;

The conditional statements contain numbers that aren't in a pattern. The numbers go up to 65,000. Also the ranges are variable and don't intersect each other. The range is stored in a SQL database:

columns: from, to
rows: [21, 59], [92, 280], etc...

I was initially thinking of creating a lookup table containing all the numbers between the ranges (e.g., [20, 21, 21, 23, ... 31, -> 45, 46 47]).

Is there a better way?

like image 953
John Avatar asked Mar 06 '23 14:03

John


1 Answers

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.

like image 158
skyboyer Avatar answered Mar 09 '23 07:03

skyboyer