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

[Dave Abrahams]

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