Wat is de complexiteit van het zoeken naar een element in een array in Swift?

De complexiteit van het zoeken naar een element in een typisch ongeordende array (bijvoorbeeld Array<Element>) in Swift is O(n), waarbij n het aantal elementen in de array is. Dit komt doordat in het slechtste geval alle elementen doorlopen moeten worden om het element te vinden.

Echter, als de array gesorteerd is, kan binair zoeken worden gebruikt, wat een complexiteit van O(log n) heeft. Swift biedt de methode binarySearch voor gesorteerde collecties.

Voorbeeld van lineair zoeken:

let array = [1, 5, 2, 8, 3]
let elementToFind = 8

for element in array {
    if element == elementToFind {
        // Element gevonden
        break
    }
}

Voorbeeld van binair zoeken in een gesorteerde array:

let sortedArray = [1, 2, 3, 5, 8]
let elementToFind = 5

if let index = sortedArray.firstIndex(where: { $0 == elementToFind }) {
    // Element gevonden op index
}