Mekkora a komplexitása egy elem keresésének egy tömbben Swiftben?

A Swiftben egy tipikus rendezetlen tömbben (például Array<Element>) való elemkeresés komplexitása O(n), ahol n a tömb elemeinek száma. Ez azért van, mert a legrosszabb esetben meg kell vizsgálni az összes elemet.

Azonban, ha a tömb rendezett, akkor bináris keresést lehet alkalmazni, amely O(log n) komplexitással rendelkezik. Swift biztosítja a binarySearch módszert rendezett kollekciókra.

Lineáris keresés példája:

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

for element in array {
    if element == elementToFind {
        // Elem megtalálva
        break
    }
}

Rendezett tömbben bináris keresés példája:

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

if let index = sortedArray.firstIndex(where: { $0 == elementToFind }) {
    // Elem megtalálva az indexen
}