lowerBound

★3の過去問やった際に書いた、SwiftのlowerBoundを今後も使いそうなのでメモ

extension RandomAccessCollection where Element: Comparable {
    
    func lowerBound(of element: Element) -> Index {
        guard first! < element else { return startIndex }
        var (left, right) = (startIndex, endIndex)
        while left < right {
            let mid = index(left, offsetBy: distance(from: left, to: right) / 2)
            if self[mid] < element {
                left = mid
            } else {
                right = mid
            }
        }
        return left == endIndex ? index(endIndex, offsetBy: -1) : left
    }
}