[swift-dev] SequenceType Binary Search Implementation

[Lorenzo Racca]

Hi all, 

I’m kinda new to this, so here’s my idea.
The other day I was building an app and had to search through a pretty big array (some 100M entries), and noticed the library function “array.contains” slowed everything down a lot. So i searched on GitHub the code and found out that "SequenceType.contains” uses Linear Search. I know that Binary Search works way better with sorted arrays (which was my situation) so here it is, why not add it to the std lib? 
I noticed it because I moved from C# where such a function is present. And I believe there is one in Java too.

I was working and I already figured out an algorithm that could really be just pasted into SequenceType.swift and make it easy for everyone. I even started benchmarking it and really, it would make a big difference. This is my code as of now:

 extension CollectionType where Generator.Element : Comparable {
    /// Returns `true` if `element` is in `self`.
    /// Collection must be sorted.
    @warn_unused_result
    public func binarySearch(element: Generator.Element) -> Bool {
        if let result = _customContainsEquatableElement(element) {
            return result
        }
        
        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 true
            }
            if ( value < element) {
                left = mid.advancedBy(1)
            }
            if (value > element) {
                right = mid
            }
        }
        return false
    }
}

Now I don’t know whether this would be accepted, useful or just even right. I don’t have the permission to pull commits to the rep, so I don’t even really know how to make it an official proposal. 

Any thoughts on this?

Lorenzo Racca
+39 345 9294756
lorenzo.racca at live.it


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20160311/38ef52f1/attachment.html>