Bisection searching algorithms

Bisect.swift

extension Array where Element: Comparable {
    // This implementations are inspired in https://github.com/python/cpython/blob/master/Lib/bisect.py
    
    /// Return the index where to insert value in the receiver, assuming the receiver is sorted
    ///
    /// - Parameters:
    ///   - value: The position of the text in current context
    ///   - min: The lower bound where to perform the search
    ///   - max: The upper bound where to perform the search
    /// - Returns: An index such that all elements in self[:i] have element < value, and all elements in
    ///            self[i:] have element >= value. Thus, if value already appears in the receiver, this will
    ///            be just before the leftmost value already there.
    func bisectLeft(_ value: Element, _ min: Int = 0, _ max: Int? = nil) -> Int {
        precondition(min >= 0, "min must be non-negative")
        
        let max = max ?? count
        guard min < max else { return min }
        
        let mid = min + (max - min) / 2
        
        if self[mid] < value { return bisectLeft(value, mid+1, max) }
        else { return bisectLeft(value, min, mid) }
    }
    
    /// Return the index where to insert value in the receiver, assuming the receiver is sorted
    ///
    /// - Parameters:
    ///   - value: The position of the text in current context
    ///   - min: The lower bound where to perform the search
    ///   - max: The upper bound where to perform the search
    /// - Returns: An index such that all elements in self[:i] have element <= value, and all elements in
    ///            self[i:] have element > value. Thus, if value already appears in the receiver, this will
    ///            be just after the rightmost value already there.
    func bisectRight(_ value: Element, _ min: Int = 0, _ max: Int? = nil) -> Int {
        precondition(min >= 0, "min must be non-negative")
        
        let max = max ?? count
        guard min < max else { return min }
        
        let mid = min + (max - min) / 2
        
        if value < self[mid] { return bisectRight(value, min, mid) }
        else { return bisectRight(value, mid+1, max) }
    }
}