• d-bugmail puremagic.com (30/30) May 05 2020 https://issues.dlang.org/show_bug.cgi?id=20798

d-bugmail puremagic.com writes:

https://issues.dlang.org/show_bug.cgi?id=20798

          Issue ID: 20798
           Summary: generic binarySearch (and others) should be available
                    in std.algorithm
           Product: D
           Version: D2
          Hardware: All
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P1
         Component: phobos
          Assignee: nobody puremagic.com
          Reporter: schveiguy yahoo.com

Let's say I have a large struct, S, and I sort an array of them according to
one field:

auto sorted = someArr.sort!((a, b) => a.field < b.field);

Now, I have this SortedRange, but I can only use binary searches and the like
if I manufacture an entire S element. But I should be able to search using
something like:

sorted.binarySearch!((a, b) => a.field < b)(fieldVal);

This is not available. In fact, the only place where binary search is
implemented in Phobos is in std.range, inside the SortedRange package.

I think binarySearch, and the other search mechanisms there, should be
available as standalone functions. They can't be proven to be correct at
compile time, but that's not important. I don't care if the answer might be
WRONG because the sort assumption is incorrect, I just shouldn't have to
reimplement binary search on my own, phobos should have this building block
available.

--