Find the border between a repeating value and any other value. Both left and right versions.

BorderBinarySearch.swift

/**
 Find the border between a repeating value and anything else.
 - Parameters:
    - key: The repeating value
    - range: The range of indexes to search for the border within.
    - f: A function to generate values.
 - Returns: The last index of key.
 */
func borderBinarySearchFLeft<T: Comparable>(lowerKey: T? = nil, range: Range<Int>, f: (Int) -> (T?)) -> Int? {
    var lBound = range.lowerBound
    var uBound = range.upperBound - 1
    
    while lBound < uBound {
        let middle = (lBound + uBound) / 2
        let value = f(middle)
        if lBound == uBound - 1, f(lBound) == lowerKey, f(uBound) != lowerKey {
            return lBound
        } else if lBound == uBound - 1 {
            return nil
        } else if value == lowerKey {
            lBound = middle
        } else {
            uBound = middle
        }
    }
    return nil
}

/**
 Find the border between any value and a specified repeating value.
 - Parameters:
    - key: The repeating value.
    - range: The range of indexes to search for the border within.
    - f: A function to generate values.
 - Returns: The first index of key.
 */
func borderBinarySearchFRight<T: Comparable>(upperKey: T? = nil, range: Range<Int>, f: (Int) -> (T?)) -> Int? {
    var lBound = range.lowerBound
    var uBound = range.upperBound - 1
    
    while lBound < uBound {
        let middle = (lBound + uBound) / 2
        let value = f(middle)
        if lBound == uBound - 1, f(uBound) == upperKey, f(lBound) != upperKey {
            return uBound
        } else if lBound == uBound - 1 {
            return nil
        } else if value == upperKey {
            uBound = middle
        } else {
            lBound = middle
        }
    }
    return nil
}