IterativeBinarySearch.swift

func binarySearchIterative<T: Comparable, E: RandomAccessCollection>(_ xs: E, target: T) -> E.Index? where E.Element == T {
    // Start with two indexes, one at the beginning
    var startIndex = xs.startIndex;
    // And one at the end
    var endIndex = xs.index(before: xs.endIndex);
    // We are done when are our indexes converge
    while startIndex < endIndex {
        // Find the midpoint between our current range
        let midPoint = xs.index(startIndex, offsetBy: xs.distance(from: startIndex, to: endIndex) / 2);
        let midValue = xs[midPoint];
        // Evaluate the middle value against our target value
        if ( target < midValue ) {
            // If the target is less than our middle value,we can narrow the search space to
            // [start, mid]
            endIndex = midPoint
        } else if ( target > midValue ) {
            // If the target is greater than our middle value,we can narrow the search space to
            // [mid, end]
            startIndex = min(midPoint, xs.index(after: startIndex))
        } else {
            // If the target is equal, we've found it
            return midPoint;
        }
    }
    // We did not find a match
    return nil;
}