BinarySearch.swift

extension Collection {
    var middleIndex: Index? {
        guard !self.isEmpty else { return nil }
        return self.index(self.startIndex, offsetBy: self.count/2)
    }

    var middle: Iterator.Element? {
        guard let middleIndex = self.middleIndex else { return nil }
        return self[middleIndex]
    }

    var lowerPart: SubSequence? {
        guard let middleIndex = self.middleIndex else { return nil }
        return self[self.startIndex..<middleIndex]
    }

    var upperPart: SubSequence? {
        guard let middleIndex = self.middleIndex else { return nil }
        let startIndex = self.index(middleIndex, offsetBy: 1)
        return self[startIndex..<self.endIndex]
    }
}

extension Collection
    where Iterator.Element: Comparable,
        SubSequence: Collection,
        SubSequence.Iterator.Element == Iterator.Element,
        SubSequence.Index == Index,
        SubSequence.SubSequence == SubSequence {

    func binarySearch(_ item: Iterator.Element) -> Index? {
        guard let middle = self.middle else { return nil }
        print("Compared '\(middle)' and '\(item)'.")

        if item == middle { return self.middleIndex }
        else if item < middle { return self.lowerPart!.binarySearch(item) }
        else { return self.upperPart!.binarySearch(item) }
    }

}

print("Small array begin ===========================================")
let smallArray = [1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71]
smallArray.binarySearch(3)
print("Small array end =============================================\n")


print("Big array 1 begin ============================================")
let bigArray1 = Array(0..<1024)
bigArray1.binarySearch(3)
print("Big array 1 end ==============================================\n")


print("Big array 2 begin ============================================")
let bigArray2 = Array(0..<5120)
bigArray2.binarySearch(787)
print("Big array 2 end ==============================================\n")