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

[Haravikk]

> On 15 Mar 2016, at 15:48, Lorenzo Racca <lorenzo.racca at live.it> wrote:
> 
> I already knew the impossibility of applying such a predicate as “$0 == 3” and I actually couldn’t quite figure out a solution.

I thought so, and I don’t think there is a way to do it, my point was really just that your swift doc comments weren’t clear on that point, then I went off at a bit of a tangent ;)

> On 15 Mar 2016, at 17:07, Jeff Hajewski <jeff.hajewski at gmail.com> wrote:
> 
>     /// Returns an index such that each element at or above the index is partitioned from below by the partition predicate
>     ///
>     /// - Parameter partitionPredicate: The partioning predicate returns `true` for elements in the collection that are
>     ///                                 ordered below, with respet to the partitioning predicate.
>     /// - Complexity: O(lg(n))
>     ///
>     /// - Returns: An index such that each element at or above the returned index evaluates as `false` with respect to `partitionPredicate(_:)`
>     @warn_unused_result
>     func lowerBound(@noescape partitionPredicate: Self.Generator.Element -> Bool) -> Index {

Should probably have "requires: Collection is sorted" or such, as a binary search can’t really guarantee correct behaviour otherwise, no matter what your predicate is. I also kind of prefer a name of isOrderedBefore for the predicate; it matches .sort() and is very specific about what it does.

> 	
>     /// Returns an index such that each element below the index is strictly less than the partition predicate
>     ///
>     /// - Parameter partitionPredicate: The partioning predicate. Returns `true` for elements in the collection that are
>     ///                             ordered below, with respet to the partitioning predicate.
>     /// - Complexity: O(lg(n))
>     ///
>     /// - Returns: An index such that each element evaluates as `false` with respect to `partitionPredicate(_:)`
>     @warn_unused_result
>     func upperBound(@noescape partitionPredicate:Self.Generator.Element -> Bool) -> Index {

Did you mean “each element above the returned index evaluates as false"?


Implementation wise they seem fine, but I think that for correctness you should be using .successor() and .advancedBy(), as not all indexes are numeric.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160315/cba8f938/attachment.html>