Wie hoch ist die Komplexität bei der Suche nach einem Element in einem Array in Swift?

Die Komplexität der Suche nach einem Element in einem typischen ungeordneten Array (z.B. Array<Element>) in Swift beträgt O(n), wobei n die Anzahl der Elemente im Array ist. Dies liegt daran, dass im schlimmsten Fall alle Elemente des Arrays durchlaufen werden müssen, um das Element zu finden.

Wenn das Array jedoch sortiert ist, kann die binäre Suche verwendet werden, die eine Komplexität von O(log n) hat. Swift stellt die Methode binarySearch für sortierte Sammlungen bereit.

Beispiel für lineare Suche:

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

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

Beispiel für binäre Suche in einem sortierten Array:

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

if let index = sortedArray.firstIndex(where: { $0 == elementToFind }) {
    // Element an Index gefunden
}