Question 52432 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript: How to return values from an array of hashes if a value is within a range

Javascript learner here.

Problem:
I have a list of hex ranges and I need to return a value if a query value is within a range. The data looks like this:

[
  {...},
  {"start": 0x3C0000, "end": 0x3FFFFF, "country": "Germany"},
  {"start": 0x044000, "end": 0x044FFF, "country": "Ghana"},
  {...}
]

I have a hex value and I would like to get the country if the hex value is between start and end.

Question 1:
What would be the most efficient way to return country if query is between start and end?

Question2:
Would there be a smarter way to format the data which would allow a faster/more efficient query?

The goal of my questions is to learn alternatives to iterating through the array with a loop.

Tags:

2

Answers


  1. 0

    A regular for loop would likely be the most efficient method.

    That being said, there is an elegant solution with filter and map.

    let res = array.filter(o => x.start <= query && query <= x.end).map(o => o.country);

    Of course, if you only want one result, then use Array#find instead.

    let res = array.find(o => x.start <= query && query <= x.end)?.country;
    Login or Signup to reply.
  2. 0

    We can’t do in O(n) if the range is not sorted. But for subsequent operations , we can do in O(log(n)) given that range end points can be arranged in a number line without any internal fragmentation. (i.e [2,3] , [5,6] contains internal fragmentation but [2,3],[3,4] doesn’t ).

    So let us take the range values in question in the form
    {{x1,y1,v1},{x2,y2,v2}...{xn,yn,vn}} and assume it is sorted. If not able to, then you can assume you can and consider it to have some null value.
    So we get the range in number line as
    [x1,y1,x2,y2,x3,y3....xn,yn] for our example where y1<=x2,y2<=x3 ( other’s comparisons are trivial as it is range endpoints ) .

    Now create a array which holds the values of range end points. You can use either 1st end point or last endpoint of range. For our example , let us take first end point. 0th index corresponds to v1 , 1th to null ( there is no value in range [y1,x2] as mentioned earlier ). Here we use bisect python standard module for efficient indexing. Feed range of breakpoints(for our example , it is x1,y1,x2,y2 .. xn,yn) with your query value (let us take xi).
    (You can apply the same logic in js )

    import bisect as bst

breakpoint = [x1,y1,x2,y2,x3,y3...xn,yn]
query = xi
rangeValueMap = [v1,null,v2,null...]

value = bst.bisect(breakpoint,query)

if value==null:
 print("No range covers the value {0}".format(query))
else:
 print("Value is %d"%(value))

    Use the index returned from bisect to get value from already created array. If it null , then the range doesn’t exist , else it does and use the value.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search