Ricerca binaria C ++
Dopo aver aperto rapidamente la shell del terminale, è necessario aver bisogno di un file C ++ per creare il codice di ricerca binario in esso. Pertanto, un semplice comando di parole chiave a una parola, i.e., "Touch", verrà utilizzato per questo motivo. Quindi, lo abbiamo usato per creare un file C ++ chiamato "Binario.CC ”e aprirlo tramite l'editor GNU Nano integrato che presenta la configurazione di Ubuntu 20.04 Sistema. Entrambi i comandi sono già stati dimostrati con l'aiuto dell'immagine qui sotto.
Esempio 01: metodo iterativo
Il primo metodo che abbiamo utilizzato qui è il metodo iterativo di ricerca binaria. Sarebbe abbastanza semplice da fare. Dopo che il file è stato aperto nell'editor Nano, abbiamo aggiunto i file di intestazione necessari per l'esecuzione del codice. Lo spazio dei nomi che deve essere standard è necessario per il codice C ++ qui. È stata creata una funzione definita dall'utente denominata "Search" per eseguire una ricerca binaria. Questa funzione definita dall'utente prende 4 argomenti nei suoi parametri, i.e., “A []” per l'array, a sinistra per gli array a sinistra, a destra per gli array a destra più valore e V per il valore da cercare nell'array “A".
All'inizio di questa funzione, abbiamo usato un semplice ciclo "mentre" per verificare se il valore più a sinistra o primo dell'array è inferiore o uguale al valore più destro (immesso alla fine) dell'array o no. Se il valore è inferiore o uguale al valore più a destra, creerà un nuovo punto nell'array, i.e., metà. Questo punto medio è stato calcolato usando sia a sinistra che a destra. Dopo che il punto medio è stato trovato, stiamo utilizzando l'istruzione "if" per verificare se il valore al medio indice di un array "A" è lo stesso del valore richiesto da controllare, i.e., "V". Se la condizione è diventata efficace e il valore "V" abbinata al valore medio-indice, restituirà l'indice medio di un array. All'inizio, il nostro array ha due metà, sinistra e destra. Quello a sinistra contiene valori più piccoli, mentre quello destro contiene i valori più grandi rispetto al valore medio-indice. Quando il valore a un punto medio è inferiore al valore da cercare, non è necessario considerare la metà sinistra di un array perché ciò conterrà valori più piccoli.
Quindi, aggiorneremo la nostra variabile sinistra con l'indice di "Mid+1". D'altra parte, se il valore centrale è maggiore del valore richiesto per essere controllato, dobbiamo ignorare la metà destra (valori più grandi) di un array. Quindi, la variabile giusta verrà aggiornata da un nuovo valore, io.e., "Mid-1". Questo processo continuerà a fare fino a quando la sinistra di un array è uguale o inferiore al punto destro di un array. Se non sono soddisfatte le condizioni, non abbiamo trovato il valore nell'array e restituendo -1 come indice al metodo principale.
Ora, è arrivato all'implementazione della funzione principale (). All'interno di questa funzione, abbiamo dichiarato un array chiamato "A" con alcuni valori interi in esso. L'array è già ordinato in ordine crescente. Quindi una variabile "V" è stata inizializzata in cui verrà salvato un valore immesso da un utente. L'istruzione Cout indica a un utente di inserire un certo numero mentre l'istruzione CIN viene utilizzata per raccogliere l'input dell'utente e salvarlo nella variabile "V".
Un'altra variabile, "N" è stata definita per ottenere la dimensione totale di un array con l'utilizzo della funzione sizeof () sull'array "A". Un'altra variabile, "Val" è stata utilizzata per ottenere l'indice dal metodo di ricerca come valore di ritorno chiamandolo. La chiamata di funzione passa l'array A, punto sinistro come 0, punto destro come intero "n-1" e il valore "v" da cercare. Se il metodo di ricerca restituisce "-1" a "Val" variabile, verrà eseguita la prima istruzione Cout; Altrimenti, il secondo verrà eseguito e visualizzerà l'indice di un valore abbinato.
Pertanto il codice richiede prima la compilation. Dopo la prima e la seconda esecuzione, l'utente ha inserito 14 e 19 e si è abbinato rispettivamente con l'indice 3 e 8, come visualizzato. Alla terza esecuzione, non ha funzionato come mostrato. Quindi, il compilatore G ++ è qui per il tuo aiuto.
Esempio 02: metodo ricorsivo
Questo riguardava il metodo iterativo di ricerca binaria in c++. Abbiamo un secondo metodo per effettuare una ricerca binaria in C ++, un metodo noto e ricorsivo. Il metodo ricorsivo sarebbe lo stesso del metodo iterativo, ma chiamiamo ricorsivamente il suo metodo di ricerca binaria. Lo spiegheremo con il codice. Quindi, apri lo stesso file e aggiorna il metodo di ricerca. Abbiamo usato lo stesso durante il loop all'interno del metodo di ricerca con le stesse condizioni in esso, i.e., istruzioni if-else, istruzione singola if e calcolo di medio punto.
L'unica modifica è stata eseguita nell'istruzione IF-Else della funzione di ricerca. Quando il valore medio è maggiore del valore da cercare nel metodo di ricerca e la condizione è soddisfatta, chiamerà lo stesso metodo di ricerca con poca modifica nei suoi parametri. Tutti i parametri saranno gli stessi tranne il valore del punto "giusto", che ora è l'indice "Mid-1". D'altra parte, quando un valore medio è inferiore al valore da cercare, io.e., "V" e la condizione non è soddisfatta, chiamerà la stessa funzione con un piccolo cambiamento nell'argomento dei parametri "Left". Il punto sinistro verrà aggiornato con l'indice di "Mid+1" ora.
Puoi vedere la funzione principale () è al 100% uguale all'esempio iterativo sopra e non ha un cambio di carattere singolo in essa.
Innanzitutto, compila questo codice ricorsivo aggiornato con G ++ e quindi eseguilo. Dopo la prima esecuzione, restituisce 3 come risultato al valore 14, mentre finora non è stato trovato alcun indice per il valore 24 dopo la seconda esecuzione.
Conclusione:
L'intero articolo di cui sopra riguarda la ricerca binaria in c++. La ricerca binaria è stata scoperta e spiegata bene con due metodi diversi, i.e., iterativo e ricorsivo. Tutti gli esempi implementati e dimostrati sono abbastanza semplici da fare e facilmente da capire, poiché ogni passo è stato spiegato abbastanza brevemente. Pertanto, stiamo ottenendo grandi speranze che questo articolo sia ugualmente vantaggioso per un utente ingenuo, nuovo ed esperto.