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@live.it