Uno degli algoritmi più fondamentali nell'informatica è l'algoritmo di ricerca binaria. È possibile implementare la ricerca binaria utilizzando due metodi: il metodo iterativo e il metodo ricorsivo. Sebbene entrambi i metodi abbiano la stessa complessità temporale, il metodo iterativo è molto più efficiente in termini di complessità spaziale.
Il metodo iterativo ha una complessità spaziale di O(1) paragonato a O(login) prodotto dal metodo ricorsivo. Quindi, come puoi implementare l'algoritmo di ricerca binaria utilizzando il metodo iterativo in C, C++ e Python?
Cos'è la ricerca binaria?
La ricerca binaria, nota anche come ricerca a mezzo intervallo, ricerca logaritmica o taglio binario, è un algoritmo che cerca e restituisce la posizione di un elemento in un array ordinato. L'elemento di ricerca viene confrontato con l'elemento intermedio. Prendendo la media dei limiti inferiore e superiore, puoi trovare gli elementi centrali.
Se l'elemento di ricerca è maggiore dell'elemento centrale, significa che tutti gli elementi sul lato sinistro sono più piccoli dell'elemento di ricerca. Quindi, il controllo si sposta sul lato destro dell'array (se l'array è in ordine crescente) aumentando il limite inferiore alla posizione successiva dell'elemento centrale.
Allo stesso modo, se l'elemento di ricerca è più piccolo dell'elemento centrale, significa che tutti gli elementi sul lato destro sono maggiori dell'elemento di ricerca. Quindi, il controllo si sposta sulla parte sinistra dell'array modificando il limite superiore nella posizione precedente dell'elemento centrale.
Ciò riduce drasticamente il numero di confronti rispetto a implementazione della ricerca lineare dove il numero di confronti è uguale al numero di elementi nello scenario peggiore. Questo metodo si rivela molto utile per trovare numeri in una rubrica o parole in un dizionario.
Ecco una rappresentazione schematica del Algoritmo di ricerca binaria:
Ricerca binaria utilizzando C
Segui questi passaggi per implementare la ricerca binaria utilizzando C:
L'intero codice sorgente del programma di ricerca binaria che utilizza C, C++, Java e Python è presente in questo Deposito GitHub.
Il programma definisce una funzione, binarioSearch(), che restituisce l'indice del valore trovato oppure -1 se non è presente:
#includere <stdio.h>
intbinarySearch(int arr[], int dimensione_arr, int numero_ricerca){
/*... */
}
La funzione funziona restringendo iterativamente lo spazio di ricerca. Poiché la ricerca binaria funziona su array ordinati, puoi calcolare il centro che altrimenti non ha senso. Puoi chiedere all'utente un array ordinato o utilizzare algoritmi di ordinamento come Bubble o Selection sort.
IL Basso E alto le variabili memorizzano gli indici che rappresentano i confini dello spazio di ricerca corrente. mezzo memorizza l'indice nel mezzo:
int basso = 0, alto = arr_size - 1, medio;Il principale Mentre() loop restringerà lo spazio di ricerca. Se il valore dell'indice basso diventa mai maggiore dell'indice alto, allora lo spazio di ricerca è stato esaurito, quindi il valore non può essere presente.
Mentre (basso <= alto) {
/* continua... [1] */
}
ritorno-1;
Dopo aver aggiornato il punto medio all'inizio del ciclo, ci sono tre possibili risultati:
- Se il valore nel punto medio è quello che stiamo cercando, restituisci quell'indice.
- Se il valore del punto medio è maggiore di quello che stiamo cercando, riduci il massimo.
- Se il valore del punto medio è inferiore, aumentare il minimo.
/* [1] ...continua */
medio = (basso + (alto - basso)) / 2;
if (arr[mid] == numero_ricerca)
ritorno metà;
altroSe (arr[mid] > search_number)
alto = medio - 1;
altro
basso = medio + 1;
Testare la funzione con l'input dell'utente. Utilizzo scanf() per ottenere input dalla riga di comando, inclusa la dimensione dell'array, il suo contenuto e un numero da cercare:
intprincipale(){
int arr[100], i, arr_size, search_number;
stampaf("Inserisci il numero di elementi: ");
scanf("%D", &arr_size);
stampaf("Inserisci i numeri: ");per (io = 0; io < arr_size; i++) {
scanf("%D", &arr[i]);
}stampaf("Inserisci il numero da cercare: ");
scanf("%D", &numero_ricerca);i = binarySearch (arr, arr_size, search_number);
se (i==-1)
stampaf("Numero non presente");
altro
stampaf("Il numero è presente alla posizione %d", io + 1);
ritorno0;
}
Se trovi il numero, visualizzane la posizione o l'indice, altrimenti un messaggio che dice che il numero non è presente.
Ricerca binaria utilizzando C++
È possibile convertire il programma C in un programma C++ importando il file Flusso di ingresso in uscita E usa lo spazio dei nomi std per evitare di ripeterlo più volte durante il programma.
#includere <iostream>
utilizzando spazio dei nomistandard;Utilizzo cout con operatore di estrazione << invece di stampaf() E cin con operatore di inserimento >> invece di scanf() e il tuo programma C++ è pronto.
stampaf("Inserisci il numero di elementi: ");
cout <<"Inserisci il numero di elementi: ";
scanf("%D", &arr_size);
cin >> arr_size;Ricerca binaria usando Python
Poiché Python non ha il supporto integrato per gli array, usa gli elenchi. Definire una funzione, binarioSearch(), che accetta tre parametri, l'elenco, la sua dimensione e un numero da cercare:
defbinarySearch(arr, arr_size, search_number):
basso = 0
alto = arr_size - 1
Mentre basso <= alto:
medio = basso + (alto-basso)//2
if arr[mid] == numero_ricerca:
ritorno mezzo
elif arr[mid] > numero_ricerca:
alto = medio - 1
altro:
basso = medio + 1
ritorno-1Inizializza due variabili, Basso E alto, da utilizzare come limite inferiore e superiore dell'elenco. Analogamente all'implementazione C, utilizzare a Mentre ciclo che restringe lo spazio di ricerca. Inizializzare mezzo per memorizzare il valore centrale dell'elenco. Python fornisce l'operatore di divisione floor(//) che fornisce il numero intero più grande possibile.
Fai i confronti e restringi lo spazio di ricerca finché il valore medio non è uguale al numero di ricerca. Se il numero di ricerca non è presente, il controllo tornerà -1.
arr_size = int (input("Inserisci il numero di elementi: "))
arr=[]
stampa("Inserisci i numeri: ", fine="")
per i nell'intervallo (0,arr_size):
arr.append(int(ingresso()))
numero_ricerca = int (input("Inserisci il numero da cercare: "))
risultato = binarySearch (arr, arr_size, search_number)
se risultato == -1:
stampa("Numero non presente")
altro:
print("Numero È presente alla posizione ", (risultato + 1))Testare la funzione con l'input dell'utente. Utilizzo ingresso() per ottenere la dimensione dell'elenco, il suo contenuto e un numero da cercare. Utilizzo intero() per convertire in numero intero l'input di stringa accettato da Python come predefinito. Per aggiungere numeri all'elenco, utilizzare il aggiungere() funzione.
Chiamata binarioSearch() e passare gli argomenti. Se trovi il numero, visualizzane la posizione o l'indice, altrimenti un messaggio che dice che il numero non è presente.
Output dell'algoritmo di ricerca binaria
Di seguito è riportato l'output dell'algoritmo di ricerca binaria quando l'elemento è presente nell'array:
Quanto segue è l'output dell'algoritmo di ricerca binaria quando l'elemento non è presente nell'array:
Impara le strutture dati e gli algoritmi fondamentali
La ricerca è uno dei primi algoritmi che impari e viene spesso richiesto in concorsi di codifica, posizionamenti e interviste. Alcuni altri algoritmi che dovresti imparare sono algoritmi di ordinamento, hashing, programmazione dinamica, corrispondenza di stringhe e test di primalità.
Inoltre, è essenziale comprendere la complessità temporale e spaziale degli algoritmi. Sono uno dei concetti più cruciali in Informatica nel determinare l'efficienza di qualsiasi algoritmo. Con la conoscenza delle strutture dati e degli algoritmi, sei destinato a creare i migliori programmi.
