Javascript:如果值在一个范围内，如何从一个哈希数组返回值

Question

在这里学习Javascript。

问题:我有一个十六进制范围的列表，如果查询值在一个范围内，我需要返回一个值。数据如下所示:

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

我有一个十六进制值，如果十六进制值在开始和结束之间，我想获得国家。

问题1:如果查询在开始和结束之间，返回国家的最有效方法是什么?

问题2:是否有一种更智能的方式来格式化数据，从而允许更快/更有效的查询?

我的问题的目的是学习用循环遍历数组的替代方法。

Answer 1

常规的for循环可能是最有效的方法。

话虽如此，filter和map有一个优雅的解决方案。

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

当然，如果您只想要一个结果，那么使用Array#find代替。

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

Answer 2

我们不能在0 (n)如果范围没有排序。但对于后续操作，我们可以在O(log(n))中进行，前提是范围端点可以排列在一个数轴上，而不存在任何内部碎片。(即[2,3]，[5,6]包含内部碎片，但[2,3]，[3,4]不包含)。

那么让我们用下面的形式来取范围值{{x1,y1,v1},{x2,y2,v2}...{xn,yn,vn}}并假设它已排序。如果不能，那么您可以假设可以，并认为它具有一些空值。数轴上的范围是[x1,y1,x2,y2,x3,y3....xn,yn]是我们的例子，y1<=x2,y2<=x3(其他的比较是微不足道的，因为它是范围端点)。

现在创建一个数组保存范围结束点的值。您可以使用范围的第一个端点或最后一个端点。对于我们的例子，让我们取第一个终点。第0个索引对应v1，第1个索引对应null(前面提到的范围[y1,x2]中没有值)。这里我们使用bisect python标准模块来实现高效索引。输入断点的范围(对于我们的示例，它是x1,y1,x2,y2 ..)Xn,yn)与您的查询值(让我们取xi)。(你可以在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))

使用从bisect返回的索引从已经创建的数组中获取值。如果为空，则表示该范围不存在，否则存在并使用该值。