0

我有一个包含值的数组，我需要找到最小值和最大值之间的所有值。我相信我需要构建某种搜索树，对吗？我想要类似的东西：

var values : number[] = tree.findBetween(min : number, max: number);

搜索的性能是主要标准。

此外，一旦构建树，我不需要更改树（添加/删除值）。

我需要什么？二叉树？平衡的搜索树？静态搜索树？

我从哪说起呢？

4

2 回答 2

1

哦，对不起，我的 Globish 有时会捉弄我。不然我看不出太多这样一个问题的难点在哪里，但是这里总是有新的答案（希望这次不会是旁边的盘子）

除此之外： 还有什么比原生 js 方法更快的呢？

const
  MaxValue = 50,
  MinValue = 10
  ;

let
  ArrayOrigin = [12, 5, 8, 130, 44, 25, 14, 42, 36 ],
  ArrayInLimits = ArrayOrigin.filter( elm=>  elm>MinValue && elm<MaxValue)
  ;

  console.log( ...ArrayInLimits );

于 2018-12-27T13:53:43.163 回答
1

感谢@bergi的回答，我真的不需要构建搜索树来对排序数组执行二进制搜索，所以我应该能够找到我的值并获取它们之间的数组部分。

只是出于好奇，我发现了一篇有趣的文章，比较了二进制搜索与普通搜索的性能 - 遍历数组。这篇文章不知何故错误地包括了将数组排序到搜索时间中的时间——只有当你有一个排序的数组时才应该使用二分搜索（如果你可以在性能关键期之前对其进行预排序）。我使用多达 1e7 个项目运行代码，排序数组的二进制搜索需要 0 毫秒，而简单地循环数组需要几十毫秒。

最后，这是我能找到的最快的二分搜索实现。 https://oli.me.uk/2014/12/17/revisiting-searching-javascript-arrays-with-a-binary-search/

感谢大家的帮助。

于 2018-12-27T12:09:40.000 回答