Quali metodi possono essere usati per trovare rapidamente un elemento in un array ordinato, minimizzando il tempo?

Per trovare rapidamente un elemento in un array ordinato, si utilizza generalmente l'algoritmo di ricerca binaria. Questo minimizza i tempi di ricerca, poiché funziona in tempo O(log n), dove n è la dimensione dell'array.

Idea della ricerca binaria:

• Confrontare l'elemento cercato con l'elemento al centro dell'array.
• Se sono uguali, l'elemento è stato trovato.
• Se l'elemento cercato è minore, cercare nella metà sinistra.
• Se è maggiore, nella metà destra.

Su iOS (Swift), puoi usare il metodo binarySearch o implementarlo tu stesso.

Esempio in Swift:

func binarySearch<T: Comparable>(_ array: [T], target: T) -> Int? {
    var low = 0
    var high = array.count - 1
    while low <= high {
        let mid = (low + high) / 2
        if array[mid] == target {
            return mid
        } else if array[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return nil
}

let sortedArray = [1, 3, 5, 7, 9]
if let index = binarySearch(sortedArray, target: 5) {
    print("Elemento trovato alla posizione \(index)")
} else {
    print("Elemento non trovato")
}