Sommario:
Definizione - Cosa significa Ricerca binaria?
Un algoritmo di ricerca binaria viene utilizzato per trovare la posizione di un valore specifico contenuto in un array ordinato. Lavorando con il principio di dividere e conquistare, questo algoritmo di ricerca può essere abbastanza veloce, ma l'avvertenza è che i dati devono essere in una forma ordinata. Funziona avviando la ricerca nel mezzo dell'array e procedendo verso il basso nella prima metà inferiore o superiore della sequenza. Se il valore mediano è inferiore al valore target, ciò significa che la ricerca deve andare più in alto, in caso contrario, deve cercare la parte discendente dell'array.
Una ricerca binaria è anche nota come ricerca a metà intervallo o ricerca logaritmica.
Techopedia spiega la ricerca binaria
Una ricerca binaria è un metodo rapido ed efficiente per trovare un valore target specifico da un set di articoli ordinati. Iniziando a metà dell'elenco ordinato, può effettivamente dimezzare lo spazio di ricerca determinando se salire o scendere l'elenco in base al valore mediano rispetto al valore target.
Ad esempio, con un valore target di 8 e uno spazio di ricerca da 1 a 11:
- Il valore mediano / medio viene trovato e il puntatore viene impostato lì, che in questo caso è 6.
- L'obiettivo di 8 viene confrontato con 6. Poiché 6 è inferiore a 8, l'obiettivo deve trovarsi nella metà superiore.
- Il puntatore viene spostato sul valore successivo (7) e confrontato con l'obiettivo. È più piccolo, quindi il puntatore si sposta sul successivo valore più alto.
- Il puntatore è ora su 8. Confrontandolo con il target, si tratta di una corrispondenza esatta, quindi il target è stato trovato.
Utilizzando la ricerca binaria, l'obiettivo doveva essere confrontato solo con tre valori. Rispetto a una ricerca lineare, sarebbe partito dal primo valore e si sarebbe spostato verso l'alto, dovendo confrontare l'obiettivo con otto valori. Una ricerca binaria è possibile solo con un set di dati ordinato; se i dati sono disposti in modo casuale, una ricerca lineare produrrebbe sempre risultati mentre una ricerca binaria verrebbe probabilmente bloccata in un ciclo infinito.
