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

[Pyry Jahkola]

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 <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/cfa59dd3/attachment.html>