[Issue 20798] generic binarySearch (and others) should be available in std.algorithm

[d-bugmail at puremagic.com]

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

--- Comment #2 from Steven Schveighoffer <schveiguy at yahoo.com> ---
(In reply to ZombineDev from comment #1)
> So where does this approach fall short? Performance, convenience, and
> accessibility?

So for example, if I wanted the S values that had the field value 42, this does
not work. Instead I have to construct an S:

    someArr
        .equalRange(S("asd", 42))
        .writeln;

Which isn't always easy or practical (S might be a large complicated struct,
with only constructors that require valid data for fields that I don't care
about).

In my code, I'm now doing:

auto idx = someArr.binarySearch!((S, v) => S.field < v)(val);
if(idx != someArr.length && someArr[idx].field == val) { /* use someArr[idx] */
}

This can be easily captured into a function (I know my values are unique so I
don't need to bother with an "equal range").

My contention is that I shouldn't have to write my own binarySearch function to
get this kind of functionality.

I suppose I could also do:

    someArr
        .map!(x => x.field)
        .enumerate
        .assumeSorted!((a, b) => a[1] < b[1])
        .equalRange(tuple(0, 42))
        .map!(a => someArr[a[0]])
        .writeln;

But again, we are talking about a LOT of work, not only in range-transform
acrobatics, but in the compiler actually calling lots of intermediary
functions, just to do a simple search an already-sorted data.

A binary search is a simple base component that should be available for
constructing more complicated items. We shouldn't hide it inside SortedRange
with a very constrained set of interfaces.

--