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

[Lorenzo Racca]

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.racca at live.it


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