array.count和array [0 ... <index]是否会减慢二进制搜索的速度？

访问number.count不是问题，因为这是数组的O（1）操作。切片numbers[0 ...< numbersHalfIndex]也不是问题。但是Array(leftHalfNumbersArray)从切片创建一个新数组，并复制所有元素。

有两种方法可以避免这种情况：

• 更新数组索引（针对当前搜索范围的上下限），而不是创建沿递归传递的数组。
• 递归递减数组切片。切片与原始数组共享元素（只要它们没有突变）。

第二种方法的演示：

func existsInArray(_ numbers: ArraySlice<Int>, _ k: Int) -> Bool {
    if numbers.isEmpty {
        return false
    }
    let numbersHalfIndex = numbers.startIndex + numbers.count / 2
    if k == numbers[numbersHalfIndex] {
        return true
    } else if k < numbers[numbersHalfIndex] {
        return existsInArray(numbers[..<numbersHalfIndex], k)
    } else {
        return existsInArray(numbers[(numbersHalfIndex + 1)...], k)
    }
}

请注意，数组切片与原始数组共享索引，因此索引不必从零开始。这numbers.startIndex就是用于索引计算的原因。

还有一个包装函数，它需要一个“真实的”数组参数：

func existsInArray(_ numbers: [Int], _ k: Int) -> Bool {
    return existsInArray(numbers[...], k)
}

正如@Leo建议的那样，您可以将其实现为一个收集方法，而不是实现两个单独的方法。集合索引不一定是整数，但是对于a而言RandomAccessCollection，索引计算保证为O（1）。您也可以将其概括为任意可比较元素的集合，而不是整数。

这是一个可能的实现：

extension RandomAccessCollection where Element: Comparable {
    /// Returns a Boolean value indicating whether the collection contains the
    /// given element. It is assumed that the collection elements are sorted
    /// in ascending (non-decreasing) order. 
    ///
    /// - Parameter element: The element to find in the collection.
    /// - Returns: `true` if the element was found in the collection; otherwise,
    ///   `false`.
    ///
    /// - Complexity: O(log(*n*)), where *n* is the size of the collection.
    func binarySearch(for element: Element) -> Bool {
        if isEmpty {
            return false
        }
        let midIndex = index(startIndex, offsetBy: count / 2)
        if element == self[midIndex] {
            return true
        } else if element < self[midIndex] {
            return self[..<midIndex].binarySearch(for: element)
        } else {
            return self[index(after: midIndex)...].binarySearch(for: element)
        }
    }
}

用法：

let numbers = [-9, 14, 37, 102]
print(numbers.binarySearch(for: 102)) // true
print(numbers.binarySearch(for: 36))  // false

另外，一种非递归方法可更新搜索范围的索引：

extension RandomAccessCollection where Element: Comparable {
    func binarySearch(for element: Element) -> Bool {
        var lo = startIndex
        var hi = endIndex

        while lo < hi {
            let mid = index(lo, offsetBy: distance(from: lo, to: hi) / 2)
            if element == self[mid] {
                return true
            } else if element < self[mid] {
                hi = mid
            } else {
                lo = index(after: mid)
            }
        }
        return false
    }
}