array.count和array [0…

Question

今天我做了一份工作测试，并被要求搜索一个整数数组，这是一个问题：

此练习的目标是检查数字中是否存在数字数组。

规格：

这些项目是按升序排列的整数。

数组最多可以包含一百万个项目

实现函数existsInArray（_数字：[Int]，_ k：Int）所以如果k属于numbers，则返回true，否则返回应该返回false。

示例：

let numbers = [-9, 14, 37, 102]
existsInArray(numbers, 102) //returns
true existsInArray(numbers, 36) //returns false

注意：请尝试节省CPU周期

好，所以我给了我下面的代码，然后等待结果

func existsInArray(_ numbers: [Int], _ k: Int) -> Bool {
    if numbers.isEmpty {
        return false
    }
    let numbersHalfIndex: Int = (numbers.count/2)
    if k == numbers[numbersHalfIndex] {
        return true
    } else if k != numbers[0] && numbers.count == 1 {
        return false
    } else if k <= numbers[numbersHalfIndex] {
        let leftHalfNumbersArray = numbers[0 ..< numbersHalfIndex]
        return existsInArray(Array(leftHalfNumbersArray), k)
    } else if k > numbers[numbersHalfIndex] {
        let rightHalfNumbersArray = numbers[numbersHalfIndex ..< numbers.count]
        return existsInArray(Array(rightHalfNumbersArray), k)
    } else {
        return false
    }
}

因此，结果证明“该解决方案在合理的时间内无法处理一百万个项目”，现在我不知道我做错了什么，因为二进制搜索的速度与f * ck一样快。

我唯一的猜测是，也许number.count或numbers [0 ... 或numbers [numbersHalfIndex ... 使一切变得慢于预期。

我绊倒了吗？

Answer 1

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

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

• 向下传递数组索引（用于上下限），而不是数组，或者
• 在递归下传递数组slices。

第二种方法的演示：

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)
    }
}

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

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