[swift-evolution] [Proposal] Add Binary Search functions to SequenceType

[Jeff Hajewski]

Thanks for bringing this back into the spotlight Pyry. A few of us have
been working on this issue here:

https://github.com/lorenzoracca/Swift-binary-search

However we have sort of stalled as we have been unable to come up with a
unary approach that Dave suggested using just Bool return values. And of
course, as you say, the three case order enum would make this a trivial
problem.

I guess the question is, do we move forward without a unary implementation
and update if/when we get a three case Order enum or do we wait on a three
case Order enum and implement a fully generic version once?

 Jeff

On Thu, Apr 28, 2016 at 7:36 AM, Pyry Jahkola <pyry.jahkola at iki.fi> wrote:

> Bringing up this topic because it became relevant with Brent
> Royal-Gordon's "[Idea] Bringing the partial/total ordering distinction
> into Comparable
> <http://thread.gmane.org/gmane.comp.lang.swift.evolution/15180>".
>
> If the `<=>` operator with a return type of a three-case `*enum* Order`,
> you can fully define the most generic versions of binary searches as:
>
>     lowerBound(compare: Self.Collection.Element -> Order) -> Index
>
> etc.
>
> On 29 Mar 2016, at 13:43, Jeff Hajewski via swift-evolution <
> swift-evolution at swift.org> wrote:
>
> I've responded below, but just for the sake of being explicit, this is
> roughly
> the signature for lowerBound, upperBound, and binarySearch I have in
> mind based on your comments of a unary predicate:
>
> lowerBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index
> upperBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index
> binarySearch(isOrderedBelow: Self.Collection.Element -> Bool) -> Bool
>
> That's the general structure - the key is that the exact same predicate is
> used in all signatures. The predicate would be defined along the lines of
> a binary predicate where one of the parameters is fixed as the search
> value.
> The unary predicate could be formed along the lines of:
>
> let binaryPred = { $0 < $1 }
> let unnaryPred = binaryPred($0, value)
>
> where value is the search value. The main point of illustrating that is
> that
> once the unary predicate is defined, we can't change the position of the
> search value within the predicate like they do in the C++ implementation.
>
>
> You're right, there's no way a Bool-returning unary comparator could
> allow you to implement anything but lowerBound. With a three-value result,
> however, you've got all you need.
>
> I've shamelessly plugged before but for the sake of proving a point, I'll
> do it once more: I think this little library we did works as a good
> starting point for a stdlib binary search API:
> https://github.com/knomi/Allsorts/blob/master/Allsorts/BinarySearch.swift
>
> — Pyry
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160428/dda083b3/attachment.html>