Binary search in Swift

BinarySearch.swift

public extension CollectionType where Index == Int, Generator.Element: Comparable {
    /// Perform a binary search for an element.
    ///
    /// - precondition: The elements in the collection are sorted.
    /// - complexity: O(log₂(n))
    ///
    /// - returns: The index of the element or `nil` if the element was not found.
    public func binarySearch(element: Generator.Element) -> Index? {
        var low = startIndex
        var high = endIndex

        while low < high {
            let currentIndex = (low + high) / 2
            let currentElement = self[currentIndex]

            if currentElement == element {
                return currentIndex
            }

            if currentElement > element {
                high = currentIndex
            } else {
                low = currentIndex + 1
            }
        }

        return nil
    }

    /// Return the first element that is not less than `element`
    ///
    /// - precondition: The elements in the collection are sorted.
    /// - complexity: O(log₂(n))
    ///
    /// - returns: An index to the lower bound of the element.
    public func lowerBound(element: Generator.Element) -> Index {
        var low = startIndex
        var high = endIndex

        while low < high {
            let currentIndex = (low + high) / 2
            let currentElement = self[currentIndex]

            if currentElement < element {
                low = currentIndex + 1
            } else {
                high = currentIndex
            }
        }
        
        return low
    }
}

BinarySearchTests.swift

import XCTest

class BinarySearchTests: XCTestCase {
    func testBinarySearch() {
        let case1: [Int] = [1, 1, 1, 1]
        XCTAssertNil(case1.binarySearch(0))
        XCTAssertNil(case1.binarySearch(2))
        XCTAssertNil(case1.binarySearch(3))
        XCTAssertNil(case1.binarySearch(4))
        XCTAssertNotNil(case1.binarySearch(1))

        let case2: [Int] = [1, 3, 3, 5]
        XCTAssertNil(case2.binarySearch(0))
        XCTAssertNil(case2.binarySearch(2))
        XCTAssertNil(case2.binarySearch(4))
        XCTAssertNotNil(case2.binarySearch(3))
        XCTAssertEqual(case2.binarySearch(1), 0)
        XCTAssertEqual(case2.binarySearch(5), 3)

        let case3: [Int] = [1, 3, 5, 7]
        XCTAssertNil(case3.binarySearch(0))
        XCTAssertNil(case3.binarySearch(2))
        XCTAssertNil(case3.binarySearch(4))
        XCTAssertEqual(case3.binarySearch(1), 0)
        XCTAssertEqual(case3.binarySearch(3), 1)
        XCTAssertEqual(case3.binarySearch(5), 2)
    }

    func testLowerBound() {
        let case1: [Int] = [1, 1, 1, 1]
        XCTAssertEqual(case1.lowerBound(0), 0)
        XCTAssertEqual(case1.lowerBound(1), 0)
        XCTAssertEqual(case1.lowerBound(2), 4)

        let case2: [Int] = [1, 3, 3, 5]
        XCTAssertEqual(case2.lowerBound(0), 0)
        XCTAssertEqual(case2.lowerBound(1), 0)
        XCTAssertEqual(case2.lowerBound(2), 1)
        XCTAssertEqual(case2.lowerBound(3), 1)
        XCTAssertEqual(case2.lowerBound(4), 3)
        XCTAssertEqual(case2.lowerBound(5), 3)
        XCTAssertEqual(case2.lowerBound(6), 4)

        let case3: [Int] = [1, 3, 5, 7]
        XCTAssertEqual(case3.lowerBound(0), 0)
        XCTAssertEqual(case3.lowerBound(1), 0)
        XCTAssertEqual(case3.lowerBound(2), 1)
        XCTAssertEqual(case3.lowerBound(3), 1)
        XCTAssertEqual(case3.lowerBound(4), 2)
        XCTAssertEqual(case3.lowerBound(5), 2)
        XCTAssertEqual(case3.lowerBound(6), 3)
    }
}