Binary Search extension on RandomAccessCollection that lets the caller do the compare on each element.

RandomAccessCollection+BinarySearch.swift

public extension RandomAccessCollection {
    func binarySearch(comparing: (Element) -> ComparisonResult) -> Element? {
        var lowerBound = startIndex
        var upperBound = endIndex
        while lowerBound < upperBound {
            let size = distance(from: lowerBound, to: upperBound)
            let midIndex = index(lowerBound, offsetBy: size / 2)

            switch comparing(self[midIndex]) {
            case .orderedSame:
                return self[midIndex]
            case .orderedAscending: // self[midIndex] is smaller than what we are looking for
                lowerBound = index(midIndex, offsetBy: 1)
            case .orderedDescending: // self[midIndex] is larger than what we are looking for
                upperBound = midIndex
            }
        }
        return nil
    }
}