javascript - 在 2 种口味列表中进行二分搜索

Question

这恰好是在 JavaScript 中，但这个问题也适用于其他语言。

我有一个很长的单词列表，按字母顺序排序，例如:

var myList= [
    {word:"abstract", flavor:"old", extraData:...},
    {word:"aircraft", flavor:"old", extraData:...},
    {word:"airplane", flavor:"new", extraData:...},
    {word:"banana", flavor:"old", extraData:...},
    {word:"calories", flavor:"new", extraData:...},
    ...
];

我的目标是使用某种搜索方法(可能是二分搜索)，以便找到有多少单词以给定的子字符串开头。在上面的示例中，给定子字符串“air” - 结果应为 2。

但是，有时我需要搜索整个列表，而其他时候我只需要搜索“旧”项目(根据上面的示例，结果应为 1)。

一个明显的解决方案是复制列表，例如:

var wholeList= [
    {word:"abstract", flavor:"old", extraData:...},
    {word:"aircraft", flavor:"old", extraData:...},
    {word:"airplane", flavor:"new", extraData:...},
    {word:"banana", flavor:"old", extraData:...},
    {word:"calories", flavor:"new", extraData:...},
    ...
];

var oldList= [
    {word:"abstract", flavor:"old", extraData:...},
    {word:"aircraft", flavor:"old", extraData:...},
    {word:"banana", flavor:"old", extraData:...},
    ...
];

这对于内存来说当然是非常浪费的。对于此类问题还有其他/已知的解决方案吗？

Answer 1

要在单词之后进行过滤:

const search ="air";
const result = myList.filter(word => word.word.substr(0,search.length) === search);

只获取旧的:

const result = myList.filter( word => word.flavor === "old");

同时两者:

const search ="air", flavor = "old";
const result = myList.filter(word => 
   word.flavor === flavor && 
   word.word.substr(0,search.length) === search
);

为了改进这一点，可以使用嵌套映射作为查找树，或者可以将它们预先分组。不过，如果您搜索多次，那就值得了。