Замедляет ли array.count и array [0 ... <index] бинарный поиск?

Question

сегодня я сделал тест на работу, и меня попросили найти массив целых чисел, вот вопрос:

Цель этого упражнения - проверить наличие числа в массив.

Технические характеристики:

Элементы представляют собой целые числа, расположенные в порядке по возрастанию .

Массив может содержать до 1 миллион элементов

Реализация функции existInArray (_ numbers: [Int], _ k: Int) , чтобы она возвращала true , если k принадлежит числам , в противном случае функция должна вернуть false .

Пример:

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

Примечание. Попробуйте сохранить циклы ЦП

Хорошо, поэтому я дал свой ответ, который является кодом ниже, и дождался результата

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 или числа [0 ... или числа [numbersHalfIndex ... делает все go медленнее, чем ожидалось.

Я спотыкаюсь или что-то в этом роде?

Редактировать: Если кому-то интересно, я протестировал свой код и код Мартина R, чтобы увидеть, какое влияние оказывает использование ArraySlice с точки зрения времени , Я использовал массив 100 000 000 итенов в порядке возрастания, начиная с 0. Вот как я захватил время:

print("////////// MINE //////////")
var startTime = CFAbsoluteTimeGetCurrent()
print(existsInArray(numbers, 0))
var timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
print("Time elapsed for mine: \(timeElapsed) s.")

print("////////// Martin R //////////")
counter = 0
startTime = CFAbsoluteTimeGetCurrent()
print(existsInArrayOptimal(numbers, 0))
timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
print("Time elapsed for Martin R: \(timeElapsed) s.")

И вот результат:

// //////// MINE //////////

true

Время, прошедшее для шахты:

1.2008800506591797 с.

////////// Martin R //////////

true

Время, прошедшее для Martin R: 0.00012993812561035156 с.

Это примерно в 1000 раз быстрее!

Answer 1

Доступ к 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, вы можете реализовать это как метод сбора вместо реализации двух отдельных методов. Индексы коллекции не обязательно являются целыми числами, но для 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
    }
}