Implementations of lowerBound and upperBound for Array.

ArrayExtensions.swift

//  Write some awesome Swift code, or import libraries like "Foundation",
//  "Dispatch", or "Glibc"

extension Array where Element: Comparable {
    
    func lowerBound(in range: CountableRange<Index>, for value: Element) -> Index {
        return lowerBound(in: range, for: value, by: <)
    }
    
    func lowerBound(for value: Element) -> Index {
        return lowerBound(in: startIndex ..< endIndex, for: value, by: <)
    }
    
    func upperBound(in range: CountableRange<Index>, for value: Element) -> Index {
        return lowerBound(in: range, for: value, by: <=)
    }
    
    func upperBound(for value: Element) -> Index {
        return lowerBound(in: startIndex ..< endIndex, for: value, by: <=)
    }
}

extension Array {
    
    func upperBound(for value: Element, by areInIncreasingOrder: (Element, Element) -> Bool) -> Index {
        return lowerBound(in: startIndex ..< endIndex, for: value, by: { (lhs, rhs) -> Bool in !areInIncreasingOrder(rhs, lhs) })
    }
    
    func upperBound(in range: CountableRange<Index>, for value: Element, by areInIncreasingOrder: (Element, Element) -> Bool) -> Index {
        return lowerBound(in: startIndex ..< endIndex, for: value, by: { (lhs, rhs) -> Bool in !areInIncreasingOrder(rhs, lhs) })
    }
    
    func lowerBound(for value: Element, by areInIncreasingOrder: (Element, Element) -> Bool) -> Index {
        return lowerBound(in: startIndex ..< endIndex, for: value, by: areInIncreasingOrder)
    }
    
    func lowerBound(in range: CountableRange<Index>, for value: Element, by areInIncreasingOrder: (Element, Element) -> Bool) -> Index {
        precondition(range.lowerBound >= startIndex && range.upperBound <= endIndex)
        
        var count = range.count
        var lowerBound = range.lowerBound
        
        while count > 0 {
            let step = count / 2
            let iter = lowerBound + step
            if areInIncreasingOrder(self[iter], value) {
                lowerBound = iter + 1
                count -= step + 1
            } else {
                count = step
            }
        }
        
        return lowerBound
    }
}

let arr = [1, 3, 5, 7, 7, 7, 9, 11, 21, 22, 22, 22]

let candidates = [-2, 0, 1, 2, 3, 7, 8, 10, 21, 22, 23]

candidates.forEach {
	let lb = arr.lowerBound(in: 0 ..< arr.count, for: $0)
	let ub = arr.lowerBound(in: 0 ..< arr.count, for: $0, by: <=)
	let ubb = arr.upperBound(in: 0 ..< arr.count, for: $0, by: <)
	let ubb1 = arr.upperBound(in: 0 ..< arr.count, for: $0)

	print($0, "->", lb, ub, ubb, ubb1)
}

results of above test codes:

-2 -> 0 0 0 0
0 -> 0 0 0 0
1 -> 0 1 1 1
2 -> 1 1 1 1
3 -> 1 2 2 2
7 -> 3 6 6 6
8 -> 6 6 6 6
10 -> 7 7 7 7
21 -> 8 9 9 9
22 -> 9 12 12 12
23 -> 12 12 12 12