Binary search for Swift arrays

array-binary-search.swift

extension Array where Element: Comparable {
    // Returns the location of the value in the array,
    // or where you should insert the value into the array.
    // If the value does not exist in the array, the Bool return value is false.
    func binarySearch(value: Element) -> (Index, Bool) {
        guard !isEmpty else {
            return (0, false)
        }
        
        if value > self.last! {
            return (endIndex, false)
        }
        if value < self.first! {
            return (startIndex, false)
        }
        
        var low = startIndex
        var high = endIndex
        while low <= high {
            let d = distance(from: low, to: high)
            let mid = index(low, offsetBy: d/2)
            if self[mid] < value {
                low = mid + 1
            } else if self[mid] > value {
                high = mid - 1
            } else {
                return (mid, true)
            }
        }
        return (low, false)
    }
}