[swift-evolution] [Proposal] Add Binary Search functions to SequenceType
Dave Abrahams
dabrahams at apple.com
Thu Apr 28 16:06:32 CDT 2016
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
More information about the swift-evolution
mailing list