I’m not sure the documentation matches the .lowerBound() and .upperBound()
behaviours accurately enough; it suggests that a bound will be found for a
predicate “match”, however if my predicate is { $0 == foo } then these won’t
actually work at all unless I get lucky and the middle element is a match, to
me this means that they will only work with comparison predicates such as { $0
> foo }, but in that case the lower bound is for the first element that is not
greater than foo, but I wouldn’t call it a “match” until I can also test it for
equality.
I’ve been doing some work recently on a sorted collection and I implemented a
binary search a bit differently. My method returns the nearest index given an
isOrderedBefore predicate, returning .endIndex if nothing matches.
Implementation below:
@warn_unused_result
public func binarySearch(withinRange theRange:Range<Index>?=nil,
isOrderedBefore:(Generator.Element) -> Bool) -> Index {
var low:Index, high:Index
if let theSpecifiedRange = theRange { low =
theSpecifiedRange.startIndex; high = theSpecifiedRange.endIndex }
else { low = self.startIndex; high = self.endIndex }
while low != high {
let mid = low.advancedBy(low.distanceTo(high) / 2)
if isOrderedBefore(self[mid]) { low = mid.successor() }
else { high = mid }
}
return low
}
What this gives me is really an insertion index, however I can implement
searching for a specific element like so:
let isOrderedBefore:(Generator.Element, Generator.Element) -> Bool
func indexOf(theElement:Equatable) -> Index? {
let theNearestIndex = self.binarySearch(){ self.isOrderedBefore($0,
theElement) }
if theNearestIndex < self.endIndex && self[theNearestIndex] ==
theElement { return theNearestIndex }
return nil
}
I can also do things like a generic insert() method like so:
func insert(theElement:Comparable) { self.insert(theElement, atIndex:
self.binarySearch(){ self.isOrderedBefore($0, theElement) }) }
(note I’ve simplified these as examples as they won’t go into CollectionType
as-is, it’s just to give you the idea).
Anyway, it seems to me that this enables simple matching of both an exact
element and the lower bound (this is what the .indexOf() above should return),
while also giving a useful value if the element isn’t found, though it does
require testing the result to be sure. When it comes to matching a specific
element, the above actually eliminates tests for equality during the search,
only having to test once at the end to confirm the result is a match.
I also added a variable starting range, as I had to handle merging two sorted
collections, in which case it’s useful to restrict the search range as you go
since there’s no point revisiting indices that you’ve passed already if the
elements are sorted properly.
The above can also perform an upper bound search by passing in a predicate such
as { $0 <= foo }, though in that case you’re performing all the extra
comparisons plus a check at the end, so there might still be an argument for
two methods, e.g nearestLowerBound() and nearestUpperBound().
Lastly, in my case I’ve defined the above method on CollectionType directly,
rather than requiring Comparable; since it takes a predicate its only
requirement is the collection is sorted prior to search it. In fact,
constraining the method to Comparable doesn’t guarantee that the collection is
sorted, only that its elements can be compared in isolation.
> On 15 Mar 2016, at 14:28, Lorenzo Racca via swift-evolution
> <swift-evolution@swift.org> wrote:
>
> Hi all,
>
> Using the library for an app with wide sorted arrays I’ve found out that
> Swift doesn’t (yet) have binary search functions.
> Standing on the fact that C++, Java and .NET all have Binary Search functions
> in their standard libs, and given the notorious difficulty to create the
> algorithm (hence the need of developers to trust the library function) I’m
> proposing to adopt these.
> I worked out some code, recalling the C++ functions binary_search,
> lower_bound and upper_bound.
> I’ve tested them and they seem all right.
>
> Also, they all return the `Index` of a found element (say, in an Array), so
> that they can be implemented to return either a boolean value, or the element
> itself. They either return nil or -1 if not any or if the predicate isn’t
> matched, but they all could surely be arranged to return nil.
> The code for binarySearch is :
>
> extension CollectionType where Generator.Element : Comparable {
> /// Returns `element.Index` if `element` is in `self`.
> /// If `element` is not in `self`, returns nil.
> @warn_unused_result
> public func binarySearch(element: Generator.Element) -> Index? {
>
> var left = startIndex
> var right = endIndex
>
> while (left != right) {
> let mid = left.advancedBy(left.distanceTo(right) / 2)
> let value = self[mid]
>
> if (value == element) {
> return mid
> }
> if (value < element) {
> left = mid.advancedBy(1)
> }
> if (value > element) {
> right = mid
> }
> }
> return nil
> }
> }
>
> lowerBound and upperBound:
>
> extension CollectionType where Generator.Element : Comparable {
> /// Returns the Index of the smallest element in collection matching
> `predicate`.
> /// If none, returns -1.
> @warn_unused_result
> func lowerBound(predicate: Generator.Element -> Bool) -> Index {
> var result = self.startIndex.advancedBy(-1)
> var low = self.startIndex
> var hi = self.endIndex
>
> while low != hi {
> let mid = low.advancedBy(low.distanceTo(hi) / 2)
>
> if predicate(self[mid]) {
> result = mid
> hi = mid
> } else {
> low = mid.advancedBy(1)
> }
> }
> return result
> }
> }
>
> extension CollectionType where Generator.Element : Comparable {
> /// Returns the Index of the biggest element in collection matching
> `predicate`.
> /// If none, returns -1.
> func upperBound(predicate: Generator.Element -> Bool) -> Index {
> var result = startIndex.advancedBy(-1)
> var low = startIndex
> var hi = endIndex
>
> while low != hi {
> let mid = low.advancedBy(low.distanceTo(hi) / 2)
>
> if predicate(self[mid]) {
> result = mid
> low = mid.advancedBy(1)
> } else {
> hi = mid
> }
> }
> return result
> }
> }
>
> If you wish to try them, usage is :
> var array : Array = [1,2,3,4,5]
>
> let a = array.upperBound{$0 < 3} //array[a] = 2
> let b = array.lowerBound{$0 > 3} //array[b] = 4
>
> What do you think? Should I commit a new file to proposals?
> Should they be added to CollectionType or SequenceType?
> It’s obviously open to discussion and change.
>
> Thank you.
>
> Best,
>
> Lorenzo Racca
> +39 345 9294756
> lorenzo.ra...@live.it <mailto:lorenzo.ra...@live.it>
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
