Ricerca binaria
Se ho il seguente vettore di 7 numeri:
0-3-4-x-10-11-12
Per trovare il valore di x,che si trova a metà,devo fare x=(inf+sup)/2=6?
mi sa di no perchè se ho
0-3-4-6-x-11-12
e voglio trovare la x,poichè A[med]
0-3-4-x-10-11-12
Per trovare il valore di x,che si trova a metà,devo fare x=(inf+sup)/2=6?
mi sa di no perchè se ho
0-3-4-6-x-11-12
e voglio trovare la x,poichè A[med]
Risposte
Dovresti vedere la x come un indice, nn come un valore, ossia la posizione che essa occupa nel vettore.
x = indice
vettore[x] = valore dell'elemento in posizione x
Ti posizioni a metà e controlli il valore vettore[x] con quello che cerchi. Se è diverso ti sposti in una delle due metà (a seconda che quello che cerchi sia maggiore o minore di quello in posizione x) e continui.
x = indice
vettore[x] = valore dell'elemento in posizione x
Ti posizioni a metà e controlli il valore vettore[x] con quello che cerchi. Se è diverso ti sposti in una delle due metà (a seconda che quello che cerchi sia maggiore o minore di quello in posizione x) e continui.
Sicuramente il valore di x sarà minore dei valori di destra e maggiore dei valori di destra.Ma come trovo tale valore?
Prima stavi facendo confusione tra indici dell'array e valori dell'array.
Ti faccio un esempio semplice: vuoi trovare un numero di telefono dall'elenco telefonico, appunto. Tu conosci il cognome e vuoi ottenere il numero di telefono (ovvero conosci il valore dell'array da ricercare e vuoi sapere la sua posizione nell'array).
1) Apri l'elenco a caso, ipotizziamo a metà (med)
2a) se il cognome che leggi viene dopo (prima) in ordine alfabetico rispetto a quello che ti interessa allora puoi scartare la seconda (prima) metà dell'elenco
2b) se il cognome che leggi è quello che ti interessa hai finito. FINE
3) il tuo nuovo elenco diventa l'elenco ridotto, ritorni a 1.
Ti faccio un esempio semplice: vuoi trovare un numero di telefono dall'elenco telefonico, appunto. Tu conosci il cognome e vuoi ottenere il numero di telefono (ovvero conosci il valore dell'array da ricercare e vuoi sapere la sua posizione nell'array).
1) Apri l'elenco a caso, ipotizziamo a metà (med)
2a) se il cognome che leggi viene dopo (prima) in ordine alfabetico rispetto a quello che ti interessa allora puoi scartare la seconda (prima) metà dell'elenco
2b) se il cognome che leggi è quello che ti interessa hai finito. FINE
3) il tuo nuovo elenco diventa l'elenco ridotto, ritorni a 1.
Beh nella ricerca binaria devi sapere quanti elementi hai ed assumere che siano ordinati.
Fatto ciò, x indica LA POSIZIONE dell'elemento che si trova a metà del vettore che consideri, ossia tutto il vettore inizialmente, la metà al secondo giro, un quarto al terzo e cosi via...
Molti si incasinano su questa parte, ma è normale
x è LA POSIZIONE
vettore[x] è il VALORE dell'elemento in quella posizione
Fatto ciò, x indica LA POSIZIONE dell'elemento che si trova a metà del vettore che consideri, ossia tutto il vettore inizialmente, la metà al secondo giro, un quarto al terzo e cosi via...
Molti si incasinano su questa parte, ma è normale
x è LA POSIZIONE
vettore[x] è il VALORE dell'elemento in quella posizione
allora $x$ può assumere indifferentemente tutti i numeri interi tali che $5<=x<=9$?
allora $x$ può assumere indifferentemente tutti i numeri interi tali che $5<=x<=9$?Non capisco il senso di questa affermazione.
Il post di luca.barletta mi sembra sufficientemente chiaro.
Fai bene attenzione al numero che indica la posizione nel vettore e all'elemento contenuto dal vettore in quella posizione.
Mi riferisco al mio esempio
Lavorando sull'esempio di ENEA84:
Il vettore V, di dimensione N=7 e già ordinato, sia: 0-3-4-6-9-11-12
il valore x da ricercare in V sia, ad esempio, x=9
all'inizio, la posizione iniziale di ricerca: inf=1 e la posizione finale di ricerca: sup=N=7
1) viene calcolato med=[(inf+sup)/2] = 4
2) si confronta V(med) con x: V(4)=9? NO
(fosse stato V(4)=9, l'algoritmo sarebbe dovuto terminare)
quindi si determina in quale metà del vettore ricercare x:
3) x>V(med)? SI', perchè 9>6
pertanto x, se apparisse in V, dovrebbe stare "a destra" della posizione med:
ridefiniamo l'ambito di ricerca, "scartando" la porzione di vettore in cui x sicuramente non c'è
e, quindi, sup resta fermo a 7 e si sposta inf:
4) inf = med+1 (inf diventa = 5)
(se fosse stato x
1) med=[(inf+sup)/2] = 6
2) V(6)=9? NO
3) x>V(med)? NO
4) sup=med-1 (sup diventa = 5)
e si ritorna a 1)
1) med=[(inf+sup)/2] = 5
2) V(5)=9? SI
e termina l'algoritmo.
Se x fosse stato un valore non presente in V, ad esempio 10, l'algoritmo
avrebbe fatto avanzare inf e indietreggiare sup, fino a che inf non fosse
diventato > sup: questa condizione garantisce che x NON è un valore contenuto in V.
Ricordo che il numero massimo di passi per trovare x o per stabilire che
x non appare in un vettore ordinato di dimensione N è pari a $[log_2N] +1$
Il vettore V, di dimensione N=7 e già ordinato, sia: 0-3-4-6-9-11-12
il valore x da ricercare in V sia, ad esempio, x=9
all'inizio, la posizione iniziale di ricerca: inf=1 e la posizione finale di ricerca: sup=N=7
1) viene calcolato med=[(inf+sup)/2] = 4
2) si confronta V(med) con x: V(4)=9? NO
(fosse stato V(4)=9, l'algoritmo sarebbe dovuto terminare)
quindi si determina in quale metà del vettore ricercare x:
3) x>V(med)? SI', perchè 9>6
pertanto x, se apparisse in V, dovrebbe stare "a destra" della posizione med:
ridefiniamo l'ambito di ricerca, "scartando" la porzione di vettore in cui x sicuramente non c'è
e, quindi, sup resta fermo a 7 e si sposta inf:
4) inf = med+1 (inf diventa = 5)
(se fosse stato x
1) med=[(inf+sup)/2] = 6
2) V(6)=9? NO
3) x>V(med)? NO
4) sup=med-1 (sup diventa = 5)
e si ritorna a 1)
1) med=[(inf+sup)/2] = 5
2) V(5)=9? SI
e termina l'algoritmo.
Se x fosse stato un valore non presente in V, ad esempio 10, l'algoritmo
avrebbe fatto avanzare inf e indietreggiare sup, fino a che inf non fosse
diventato > sup: questa condizione garantisce che x NON è un valore contenuto in V.
Ricordo che il numero massimo di passi per trovare x o per stabilire che
x non appare in un vettore ordinato di dimensione N è pari a $[log_2N] +1$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo