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

[Dave Abrahams]

on Thu Apr 28 2016, Jeff Hajewski <swift-evolution at swift.org> wrote:

> Dave - I think it boils down to a gap in communication. We were under the
> impression that the goal was a pure extension of CollectionType, without making
> any requirements on Generator.Element (i.e., your requiring it to be
> comparable), where binary search, lower bound, and upper bound all work with the
> same unary predicate. 
> Of course, as you demonstrated, it is trivial to implement when
> Generator.Element is Comparable, but if you relax that requirement it
> is not possible to create a set of functions (binary search, lower
> bound, upper bound) that all take the same unary predicate. 

I'm sorry if I gave you the wrong impression.  What I posted was exactly
what I had in mind.

> We ultimately came up with a slightly different approach, implementing
> binary search similar to your example, but a different take on lower
> bound, upper bound, and range. I suppose we should just send out our
> proposal and get everyone's take on it.
>
> Jeff
>
> On Thu, Apr 28, 2016 at 5:06 PM, Dave Abrahams via swift-evolution
> <swift-evolution at swift.org> wrote:
>
>     on Thu Apr 28 2016, Jeff Hajewski
>     <swift-evolution at swift.org> wrote:
>
>     > 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?
>
>     Or you could just do it like this (Swift 2.2-compatible). Am I missing
>     something?
>
>     extension CollectionType {
>     /// Returns the index of the first element satisfying `predicate`,
>     /// or `endIndex` if no such element exists.
>     ///
>     /// - Requires: `self` is partitioned with respect to `predicate`;
>     /// that is, there exists an index `i` in `startIndex...endIndex`
>     /// such that `predicate` returns `false` for every element of
>     /// `self[startIndex..<i]` and returns `true` for every element
>     /// of `self[i..<endIndex]`.
>     @warn_unused_result
>     public func binarySearch(
>     predicate: (Self.Generator.Element)->Bool
>     ) -> Index {
>     var len = count
>     var min = startIndex
>     while len > 0 {
>     let half = len/2
>     let middle = min.advancedBy(half)
>
>     if !predicate(self[middle]) {
>     min = middle.successor()
>     len -= half.successor()
>     } else {
>     len = half
>     }
>     }
>     return min
>     }
>     }
>
>     extension CollectionType where Generator.Element : Comparable {
>     /// Returns the index of the first element greater than or equal to
>     /// `target`, or `endIndex` if no such element exists.
>     ///
>     /// - Requires: `self` is sorted.
>     @warn_unused_result
>     public func lowerBound(target: Self.Generator.Element) -> Index {
>     return binarySearch { $0 >= target }
>     }
>
>     /// Returns the index of the first element greater than
>     /// `target`, or `endIndex` if no such element exists.
>     ///
>     /// - Requires: `self` is sorted.
>     @warn_unused_result
>     public func upperBound(target: Self.Generator.Element) -> Index {
>     return binarySearch { $0 > target }
>     }
>     }
>
>     //===--- TEST IT -
>     ---------------------------------------------------------===//
>     import Darwin
>     for _ in 0..<1000 {
>     // build a sorted array of up to 30 values in the range 0..<10
>     var a : Array<Int> = []
>     for _ in 0..<arc4random_uniform(30) {
>     a.append(Int(arc4random_uniform(10)))
>     }
>     a.sortInPlace()
>
>     print(a)
>
>     for i in -3...14 {
>     let l = a.lowerBound(i)
>     let u = a.upperBound(i)
>     assert(l >= 0)
>     assert(u <= a.count)
>     assert(l <= u)
>     if l > 0 {
>     assert(a[l - 1] < i)
>     }
>     if l < a.count {
>     assert(a[l] >= i)
>     }
>     if u > 0 {
>     assert(a[u - 1] <= i)
>     }
>     if u < a.count {
>     assert(a[u] > i)
>     }
>     }
>     }
>
>     --
>     Dave
>
>     _______________________________________________
>     swift-evolution mailing list
>     swift-evolution at swift.org
>     https://lists.swift.org/mailman/listinfo/swift-evolution
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-- 
Dave