RecursiveBinarySearch.swift

func binarySearchRecursive<T: Comparable, E: RandomAccessCollection>(_ xs: E, target: T, start _start: E.Index? = nil, end _end: E.Index? = nil) -> E.Index? where E.Element == T {
    // Base cases
    guard !xs.isEmpty else { return nil; }
    guard xs.count > 1 else {
	return xs[xs.startIndex] == target ? xs.startIndex : nil
    }

    // Start with two indexes, optionally supplied
    let startIndex = _start ?? xs.startIndex;
    let endIndex = _end ?? xs.endIndex;
    // Calculate the middle index
    let midPoint = xs.index(startIndex, offsetBy: xs.distance(from: startIndex, to: endIndex) / 2);
    let midValue = xs[midPoint];

    // Compare middle value to target value
    if ( target < midValue ) {
        // recursively search the new search space of: [start, mid]
        return binarySearchRecursive(xs, target: target, start: startIndex, end: midPoint);
    } else if ( target > midValue ) {
	// recursively search the new search space of [mid, end] 
        return  binarySearchRecursive(xs, target: target, start: midPoint, end: endIndex)
    } else {
        // If the target is equal, we've found it
        return midPoint;
    }
}