问题 二进制搜索D 2.0(Phobos)?


它只是我,还是在Phobos中没有二进制搜索功能?我有一个预先排序的数组,我想用我自己的比较器函数进行搜索,但我在std.algorithms或std.containers中找不到任何东西。

谢谢!


10707
2018-01-07 03:54


起源



答案:


使用 SortedRange 从 std.range

从中受贿 http://www.digitalmars.com/d/2.0/phobos/std_range.html#SortedRange

auto a = [ 1, 2, 3, 42, 52, 64 ];
auto r = assumeSorted(a);
assert(r.canFind(3));
assert(!r.canFind(32));

16
2018-01-07 04:10



啊,你必须使用“assumeSorted”......没想到,谢谢! :) - Mehrdad
find() (因此 canFind())实际上非常聪明,根据给定的输入类型使用不同的算法。为了使二进制搜索起作用,必须对数据进行排序 assumeSorted() 使它成为,然后 find() 和 canFind() 很聪明,知道二进制搜索是最好的搜索,这就是他们所做的。 - Jonathan M Davis
如果您只是尝试进行二分查找,那么它根本不直观。 - Trass3r
已经很晚了,我很累,但我怀疑设计是好的,我的意思是,为排序概念带来强大的打字,并将“你想做什么”与“如何完成”分开似乎很酷。 D只需要像这样的问题和答案,以便人们可以通过Google快速学习这些东西。 - Qwertie


答案:


使用 SortedRange 从 std.range

从中受贿 http://www.digitalmars.com/d/2.0/phobos/std_range.html#SortedRange

auto a = [ 1, 2, 3, 42, 52, 64 ];
auto r = assumeSorted(a);
assert(r.canFind(3));
assert(!r.canFind(32));

16
2018-01-07 04:10



啊,你必须使用“assumeSorted”......没想到,谢谢! :) - Mehrdad
find() (因此 canFind())实际上非常聪明,根据给定的输入类型使用不同的算法。为了使二进制搜索起作用,必须对数据进行排序 assumeSorted() 使它成为,然后 find() 和 canFind() 很聪明,知道二进制搜索是最好的搜索,这就是他们所做的。 - Jonathan M Davis
如果您只是尝试进行二分查找,那么它根本不直观。 - Trass3r
已经很晚了,我很累,但我怀疑设计是好的,我的意思是,为排序概念带来强大的打字,并将“你想做什么”与“如何完成”分开似乎很酷。 D只需要像这样的问题和答案,以便人们可以通过Google快速学习这些东西。 - Qwertie