[swift-evolution] [Discussion] Binary search, lower bound, upper bound, equal range

[Jeff Hajewski]

Hello,

I am working on SR-368 <https://bugs.swift.org/browse/SR-368> and am hoping to get some feedback from the community.

Description
Implement analogs to C++’s binary_search, lower_bound, upper_bound, and equal_range algorithms.

Initial Proposal
I propose adding four methods for generic Array and adding four methods for Arrays that conform to Comparable:


Array
@warn_unused_result
func lowerBound(value: Array.Element, @noescape isOrderedBefore: (lhs: Array.Element, rhs: Array.Element) -> Bool) -> Int?

@warn_unused_result
func upperBound(value: Array.Element, @noescape isOrderedBefore: (lhs: Array.Element, rhs: Array.Element) -> Bool) -> Int?

@warn_unused_result
func binarySearch(value: Array.Element, @noescape isOrderedBefore:(lhs: Array.Element, rhs: Array.Element) -> Bool) -> Bool

@warn_unused_result
func equalRange(value: Array.Element, @noescape isOrderedBefore: (lhs: Array.Element, rhs: Array.Element) -> Bool) -> Range<Int>?


Array: Comparable
@warn_unused_result
func lowerBound(value: Array.Element) -> Int?

@warn_unused_result
func upperBound(value: Array.Element) -> Int?

@warn_unused_result
func binarySearch(value: Array.Element) -> Bool

@warn_unused_result
func equalRange(value: Array.Element) -> Range<Int>?

Discussion
The main issue I’d like to discuss is how do we want to add these to Swift? My thoughts are as follows:

These should be as generic as possible. I initially started at the CollectionType level but it seemed that the problem was ultimately reduced to an Array (through the use of various protocols, etc.). For example, suppose we implemented these methods as an extension to CollectionType, if we were to try and call binarySearch on a set, we would first need to sort the set, which would return an array, and then we would call binarySearch on that array. Similarly, it seems at the SequenceType level the problem ultimately reduces to using Array.
Does it make sense to handle these as public functions? I tend to think not as it seems less idiomatic.
I suggest eight implementations similar to how sort() is handled. If the calling array’s elements conform to Comparable, then no isOrderedBefore closure is required since we can use “<“, otherwise the user should supply a closure to allow the algorithm determine how the array elements are ordered.
Similar to the C++ implementations, I avoid recursion and favor while-loops
These methods should be preconditioned on the calling array be partitioned with respect to the passed value. As far as I’m aware, there is no “isPartitioned(value:)” method currently available. Should we add this as well? We could use this functionality and not add a isPartitioned method but if we are adding this functionality is there a good reason not to give the public access? The alternative is to not set a precondition and document that the results may not be valid if the calling array is not partitioned with respect to value. I favor the preconditioning approach.

Any and all feedback is greatly appreciated!

Thanks
Jeff
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160215/a54eab68/attachment.html>