Skip to content

Instantly share code, notes, and snippets.

@Vadim-Yelagin
Created November 12, 2015 14:37
Show Gist options
  • Save Vadim-Yelagin/4c4ed9048f254a5efae7 to your computer and use it in GitHub Desktop.
Save Vadim-Yelagin/4c4ed9048f254a5efae7 to your computer and use it in GitHub Desktop.
Binary search extension for CollectionType in Swift
extension CollectionType where Index: RandomAccessIndexType {
/// Finds such index N that predicate is true for all elements up to
/// but not including the index N, and is false for all elements
/// starting with index N.
/// Behavior is undefined if there is no such N.
func binarySearch(predicate: Generator.Element -> Bool) -> Index {
var low = startIndex
var high = endIndex
while low != high {
let mid = low.advancedBy(low.distanceTo(high) / 2)
if predicate(self[mid]) {
low = mid.advancedBy(1)
} else {
high = mid
}
}
return low
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment