Qual è la differenza tra ricerca lineare e ricerca binaria?

Question

Qual è la differenza tra ricerca lineare e ricerca binaria?

Answer 1

A linear search un elenco, un elemento alla volta, senza saltare. In termini di complessità questa è una ricerca O(n) - il tempo impiegato per cercare l'elenco si ingrandisce alla stessa velocità dell'elenco.

A binary search è quando si inizia nel mezzo di un elenco ordinato e si vede se è maggiore o minore del valore che si sta cercando, il che determina se il valore è nella prima o nella seconda metà dell'elenco . Salta a metà della sottolista e confronta di nuovo ecc. Questo è praticamente il modo in cui gli umani di solito cercano una parola in un dizionario (anche se usiamo euristiche migliori, ovviamente - se stai cercando "gatto" non lo fai iniziare a "M"). In termini di complessità questa è una ricerca O(log n): il numero di operazioni di ricerca cresce più lentamente rispetto a quello della lista, poiché dimezza lo "spazio di ricerca" con ciascuna operazione.

Ad esempio, si supponga di cercare U in un elenco di lettere A-Z (indice 0-25; stiamo cercando il valore nell'indice 20).

Una ricerca lineare avrebbe chiesto:

list[0] == 'U'? No.
list[1] == 'U'? No.
list[2] == 'U'? No.
list[3] == 'U'? No.
list[4] == 'U'? No.
list[5] == 'U'? No.
... list[20] == 'U'? Sì. Finito.

La ricerca binaria avrebbe chiesto:

Confronta list[12] ('M') con 'U': Più piccolo, guarda più avanti. (Intervallo = 13-25)
Confronta list[19] ('T') con 'U': più piccolo, guarda più avanti. (Intervallo = 20-25)
Confronta list[22] ('W') con 'U': più grande, guarda prima. (Intervallo = 20-21)
Confronta list[20] ('U') con 'U': trovato! Finito.

Confrontando i due:

• La ricerca binaria richiede i dati di input da ordinare; ricerca lineare non
• La ricerca binaria richiede un confronto ; la ricerca lineare richiede solo confronti di uguaglianza
• La ricerca binaria ha complessità O (log n); la ricerca lineare ha la complessità O (n) come discusso in precedenza
• La ricerca binaria richiede l'accesso casuale ai dati; ricerca lineare richiede solo accesso sequenziale (questo può essere molto importante - significa una ricerca lineare può flusso dati di dimensione arbitraria)

Answer 2

pensare ad esso come due diversi modi di trovare la strada in una rubrica.Una ricerca lineare inizia all'inizio, leggendo ogni nome fino a trovare quello che stai cercando. Una ricerca binaria, d'altra parte, è quando apri il libro (di solito nel mezzo), guarda il nome in cima alla pagina e decidi se il nome che stai cercando è più grande o più piccolo di quello che hai stai cercando. Se il nome che stai cercando è più grande, allora continui a cercare la parte superiore del libro proprio in questo modo.

Answer 3

Una ricerca lineare inizia all'inizio di un elenco di valori e controlla 1 per 1 in ordine per il risultato che si sta cercando.

Una ricerca binaria inizia nel mezzo di un array ordinato e determina quale lato (se esiste) il valore che si sta cercando è attivo. Quella "metà" dell'array viene quindi ricercata di nuovo nello stesso modo, dividendo i risultati a metà per due ogni volta.

Answer 4

vorrei aggiungere una differenza:

Per i valori di ricerca lineare non devono essere ordinati.

Ma per la ricerca binaria i valori devono essere ordinati.

Answer 5

La ricerca lineare, definita anche ricerca sequenziale, esamina ciascun elemento in sequenza dall'inizio per vedere se l'elemento desiderato è presente nella struttura dati. Quando la quantità di dati è piccola, questa ricerca è veloce. È facile, ma il lavoro necessario è proporzionale alla quantità di dati da cercare. Il numero di elementi raddoppia il tempo per cercare se l'elemento desiderato non è presente.

La ricerca binaria è efficiente per un array più grande. In questo controlliamo l'elemento centrale. Se il valore è più grande di quello che stiamo cercando, allora guarda nel primo tempo, altrimenti guarda nella seconda metà. Ripeti fino a trovare l'oggetto desiderato. La tabella deve essere ordinata per la ricerca binaria. Elimina metà dei dati ad ogni iterazione. Il logaritmo.

Se abbiamo 1000 elementi da cercare, la ricerca binaria richiede circa 10 passaggi, la ricerca lineare 1000 passaggi.

Answer 6

ricerca binaria viene eseguito in O (log n) tempo, mentre ricerca lineare viene eseguito in O (n) volte in tal modo la ricerca binaria ha prestazioni migliori

Answer 7

Assicurati di deliberare sul fatto che la vittoria della ricerca più veloce binaria vale il costo di mantenere la lista ordinata (per poter usare la ricerca binaria). Cioè se hai molte operazioni di inserimento/rimozione e solo una ricerca occasionale la ricerca binaria potrebbe essere più lenta della ricerca lineare.

Answer 8

Prova questo: selezionare un nome casuale "Cognome, Nome" e cercarlo nella rubrica.

1a volta: iniziare dall'inizio del libro, leggere i nomi finché non lo si trova, oppure trovare il luogo in cui si sarebbe verificato in ordine alfabetico e notare che non è lì.

2a volta: apri il libro a metà strada e guarda la pagina. Chiediti, se questa persona si trova a sinistra oa destra. Qualunque sia, prendi 1/2 e trova il mezzo. Ripeti questa procedura fino a trovare la pagina in cui dovrebbe trovarsi la voce, quindi applica lo stesso processo alle colonne oppure cerca semplicemente linearmente i nomi sulla pagina come in precedenza.

Tempo entrambi i metodi e riportare!

[considerare anche ciò che approccio è migliore se hai a disposizione solo un elenco di nomi, non ordinato ...]

Answer 9

Una ricerca lineare guarda giù una lista, un elemento alla volta, senza salti.In termini di complessità questa è una ricerca O (n) - il tempo impiegato per cercare l'elenco si ingrandisce alla stessa velocità della lista.

Una ricerca binaria è quando inizi nel mezzo di un elenco ordinato e vedi se è maggiore o minore del valore che stai cercando, il che determina se il valore è nella prima o nella seconda metà del elenco. Salta a metà della sottolista e confronta di nuovo ecc. Questo è praticamente il modo in cui gli umani di solito cercano una parola in un dizionario (anche se usiamo euristiche migliori, ovviamente - se stai cercando "gatto" non lo fai iniziare a "M"). In termini di complessità questa è una ricerca O (log n): il numero di operazioni di ricerca cresce più lentamente rispetto a quello della lista, poiché dimezza lo "spazio di ricerca" con ciascuna operazione.

Answer 10

Una ricerca lineare funziona esaminando ciascun elemento in un elenco di dati finché non trova il target o raggiunge la fine. Ciò si traduce in prestazioni O (n) in un determinato elenco. Una ricerca binaria viene fornita con il prerequisito che i dati devono essere ordinati. Possiamo sfruttare queste informazioni per ridurre il numero di elementi che dobbiamo esaminare per trovare il nostro obiettivo. Sappiamo che se guardiamo un elemento casuale nei dati (diciamo l'elemento centrale) e quell'elemento è maggiore del nostro obiettivo, allora tutti gli elementi a destra di quell'oggetto saranno anche maggiori del nostro obiettivo. Ciò significa che dobbiamo solo guardare la parte sinistra dei dati. Fondamentalmente, ogni volta che cerchiamo l'obiettivo e perdiamo, possiamo eliminare metà degli oggetti rimanenti. Questo ci dà una buona complessità di tempo O (log n).

Basta ricordare che i dati di ordinamento, anche con l'algoritmo più efficiente, saranno sempre più lenti di una ricerca lineare (gli algoritmi di ordinamento più veloci sono O (n * log n)). Quindi non dovresti mai ordinare i dati solo per eseguire una singola ricerca binaria in seguito. Ma se si eseguono molte ricerche (ad esempio almeno ricerche O (log n)), potrebbe essere utile ordinare i dati in modo da poter eseguire ricerche binarie. Potresti anche considerare altre strutture di dati come una tabella hash in tali situazioni.

Answer 11

Linear Search esamina gli elementi finché non trova il valore cercato.

Efficienza: O(n)

Esempio codice Python:

test_list = [1, 3, 9, 11, 15, 19, 29] 
test_val1 = 25 
test_val2 = 15 

def linear_search(input_array, search_value): 
    index = 0 
    while (index < len(input_array)) and (input_array[index] < search_value): 
     index += 1 
    if index >= len(input_array) or input_array[index] != search_value: 
     return -1 

    return index 


print linear_search(test_list, test_val1) 
print linear_search(test_list, test_val2) 

Binary Search trova l'elemento centrale dell'array. Controlla che il valore medio sia maggiore o minore del valore di ricerca. Se è più piccolo, ottiene il lato sinistro dell'array e trova l'elemento centrale di quella parte. Se è maggiore, ottiene la parte giusta dell'array. Fa scorrere l'operazione finché non trova il valore cercato. O se non c'è alcun valore nell'array termina la ricerca.

Efficienza: O(logn)

Esempio codice Python:

test_list = [1, 3, 9, 11, 15, 19, 29] 
test_val1 = 25 
test_val2 = 15 

def binary_search(input_array, value): 
    low = 0 
    high = len(input_array) - 1 
    while low <= high: 
     mid = (low + high)/2 
     if input_array[mid] == value: 
      return mid 
     elif input_array[mid] < value: 
      low = mid + 1 
     else: 
      high = mid - 1 

    return -1 


print binary_search(test_list, test_val1) 
print binary_search(test_list, test_val2) 

Inoltre è possibile vedere le informazioni visualizzate sulla lineari e ricerca binaria qui: https://www.cs.usfca.edu/~galles/visualization/Search.html