Ricerca binaria

La ricerca è l'atto di cercare un particolare elemento in un dato insieme di elementi. Sembra simile all'ordinamento, ma invece di fare un intero set di elementi, stiamo solo cercando un elemento.

Ci sono generalmente due modi comuni di ricerca: ricerca lineare e ricerca binaria . Il primo è il più semplice e utile solo se l'elenco che stai cercando non è affatto ordinato. Basta passare da 0 alla lunghezza dell'array e controllare uno per uno se è l'elemento che stai cercando. Quindi la sua complessità temporale è O(n).

Questa è l'implementazione della ricerca lineare in Swift:

func linearSearch<T: Equatable>(_ a: [T], _ key: T) -> Int? {
for i in 0 ..< a.count {
        if a[i] == key {
            return i
        }
    }
return nil
}

linearSearch(numbers, 43)  // returns 15

Ecco una visualizzazione dell'algoritmo di ricerca binaria dove 7 è il valore target:

Da Wikipedia

Vediamo come funziona in pratica:

func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? {
if range.lowerBound >= range.upperBound {
        return nil
    } else {
        let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2

        if a[midIndex] > key {
            return binarySearch(a, key: key, range: range.lowerBound ..< midIndex)
        } else if a[midIndex] < key {
            return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound)
        } else {
            return midIndex
        }
    }
}

let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
binarySearch(numbers, key: 43, range: 0 ..< numbers.count)  // gives 13

Ecco un'implementazione iterativa della ricerca binaria in Swift:

func binarySearch<T: Comparable>(_ a: [T], key: T) -> Int? {
var lowerBound = 0
    var upperBound = a.count
while lowerBound < upperBound {
        let midIndex = lowerBound + (upperBound - lowerBound) / 2
if a[midIndex] == key {
            return midIndex
        } else if a[midIndex] < key {
            lowerBound = midIndex + 1
        } else {
            upperBound = midIndex
        }
    }
return nil
}

Infine, puoi usarlo in questo modo:

let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
binarySearch(numbers, key: 43)  // gives 13

La complessità temporale dell'algoritmo di ricerca binaria (in entrambi gli approcci) è O(log n) poiché il tempo di esecuzione cresce in proporzione al logaritmo della dimensione dell'input. La complessità temporale nel migliore dei casi sarebbe O (1) quando l'indice centrale corrisponderebbe direttamente al valore desiderato.

La complessità spaziale nell'iterativo è O(1) . Mentre nel metodo ricorsivo, la complessità spaziale è O(log n) .

Grazie per aver dedicato del tempo a leggere questo articolo.

Suggested posts

“Quell'isoletta cambia tutto”

Come abbiamo progettato Lyft Live Activities per migliorare l'esperienza del ciclista

“Quell'isoletta cambia tutto”

Un punto di svolta per il rideshare Di tutte le cose che facciamo in Lyft, la coreografia dei pickup tra motociclisti e conducenti è una delle più complesse e consequenziali. L'inchiodamento di questa coreografia dipende dal fatto che Lyft faccia bene molte cose, ma è essenziale semplicemente mantenere i ciclisti al passo.

Ciclo di vita dell'app

Ciclo di vita dell'app

: Ciclo dall'avvio dell'app allo spegnimento: usabilità gestendo la memoria o i dati ⬆️ La sicurezza può essere elaborata UIApplication, situazione AppDelegate: definisce le funzioni in cui l'oggetto AppDelegate riceve il messaggio inviato dall'oggetto UIApplication ed esegue ciascuna Non in esecuzione: lo stato in cui l'app non è in esecuzione Inattivo: Lo stato in cui l'app è in esecuzione ma non vengono ricevuti eventiActive: lo stato in cui l'app è in esecuzione e si verifica un eventoBackground: lo stato in cui l'app è in background ma il codice viene eseguitoSuspened: lo stato in cui l'app è in background e non esegue codice per essere funzioni delegate nel file AppDelegate.swift SceneDelegate Per rispondere bene alla funzione di scena multipla supportata da iOS 13 in poi AppDelegate / SceneDelegate AppDelegate 1.

Related posts

Finanziare la rimozione del carbonio nell'anno fiscale 24

La ripartizione delle richieste di stanziamenti di Carbon180 in tutti i percorsi

Finanziare la rimozione del carbonio nell'anno fiscale 24

Di Alyson Lee, consulente per gli affari governativi Il processo di stanziamento annuale del governo federale è fondamentale per i nostri sforzi per finanziare la rimozione dell'anidride carbonica (CDR). Ogni anno, Carbon180 invia richieste a vari uffici congressuali per aiutare a guidare dove fluiranno i dollari del prossimo anno.

La bugia del cowboy

Come le megacorporazioni hanno venduto agli americani una grossa falsità

La bugia del cowboy

È una brillante mattina d'oro sulle dolci colline dell'ovest, mentre i primi raggi di sole illuminano l'erba ghiacciata sulle pianure. Una mandria di placidi bovini Angus, nerissimi e massicci, si staglia contro l'alba mentre percorrono un sentiero battuto verso un luogo che tutti conoscono bene; il bancone della colazione.

3 modi comprovati per migliorare la tua abilità di scrittura

I vantaggi della scrittura e le strategie per aiutarti a farlo

3 modi comprovati per migliorare la tua abilità di scrittura

Nel 2022, con il rilascio di GPT-3, l'abilità di scrittura sembra diventare meno importante. Con l'intelligenza artificiale, anche le persone con una scrittura scadente possono generare personale di qualità.

Raccolta di OSINT per la caccia alle minacce

Raccolta di OSINT per la caccia alle minacce

Ehi, cibernetici! Bentornati alla serie OSINT per la caccia alle minacce. Nel primo articolo, ti ho fornito una panoramica di OSINT e della sua importanza nella caccia alle minacce.