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

Jeff Hajewski jeff.hajewski at gmail.com
Mon Feb 15 14:35:26 CST 2016


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

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:

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

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

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

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

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

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

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

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

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!

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

More information about the swift-evolution mailing list