★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 } }