Newsgroup: it.comp.java
Titolo: HelpMe Algoritmo di ricerca binaria, con risultato speciale!!!

salve a tutti e scusate se vi rompo con tanti messaggi.
Devo realizzare un piccolo esercizio di programmazione però mi trovo un po 
in difficoltà.
Praticamente, uhm... faccio prima ad incollare la traccia:
" Mediante diagrammi di Nassi-Schneidermann,
  fornire la specifica di un algoritmo di ricerca binaria che, dati in input
  un vettore ordinato di stringhe senza duplicati ed una chiave da
  cercare,restituisca la posizione della chiave cercata se 
presente,altrimenti
  quella che avrebbe nel caso fosse inserita. "
Ovviamente non voglio l'esercizio realizzato, ma vorrei semplicemente sapere
come potrei fare per risolvere solo l'ultima parte, cioè:
se nell'array non è presente l'elemento da cercare, come cavolo faccio a
sapere la posizione in cui sarebbe duvuto stare se c'èra( scusate il gioco
di parole) ???
Grazie per una vostra risposta ciao a tutti.

non ha senso la domanda che fai, vuol dire che non hai proprio idea di cosa
sia la ricerca binaria...


Vedi che quella è una traccia di un esame all'università fatta dal 
professore, per cui non credo proprio che non abbia senso, e cmq io credo 
che un professore non chieda cose impossibili!!!
e cmq se conosci le api ti accorgeresti che il metodo Arrays.binarySearch(un 
array, la kyave da cercare) di Java già lo fa, se il valore chiave non è 
presente restituisce la possibile posizione in cui si dovrebbe trovare, 
cioè -k-1 dove k è la posizione prima della quale andrebbe inserito 
l'elemento.
Ad esempio:
int[] a ={1,4,9};
int v=7;
int pos= Arrays.binarySearch(a,v);
   //restituisce -3; v andrebbe inserito prima della posizione 2
Ciao a tutti!!!

 ha scritto nel messaggio
news:44a5e214$0$3112$4faf...@reader1.news.tin.it...


Comunque, visto che siamo qua...
la ricerca binaria opera su un vettore ordinato, questo è fondamentale.
Occorre memorizzare gli indici Inf (il primo elemento del vettore), Sup
(l'ultimo elemento del vettore) e Med (l'elemento a metà).
A questo punto si effettua un confronto tra l'elemento all'indice Med e
l'elemento da cercare, che chiameremo X.
Se X è minore di Med, vuol dire che si troverà in una posizione compresa tra
Inf (il primo elemento) e Med (che è sicuramente superiore), al contrario se
X è maggiore di Med, si troverà sicuramente in una posizione compresa tra
Med e Sup (l'ultimo elemento); questo si può dire alla luce del fatto che il
vettore è ORDINATO (il primo elemento è anche il MINIMO, l'ultimo elemento è
sicuramente anche il MASSIMO).
Fatto questo, è ovvio, si può eliminare circa la metà degli elementi del
vettore, perchè sappiamo già che l'elemento non può trovarsi in quella metà.
Supponiamo che l'elemento si trovi nella metà superiore, a questo punto:
Inf = Med;
Med= (Inf + Sup)/2;
se invece si trovava nella metà inferiore:
Sup = Med;
Med = (Inf+Sup)/2;
Si itera tutto ciò finchè l'indice Sup non coincide con l'indice Inf, ora ti
è più chiaro perchè è banale sapere la posizione in cui sarebbe stato
l'elemento?

 Si itera tutto ciò finchè l'indice Sup non coincide con l'indice Inf
Credo sia più corretto usare la ricorsione, non perché sia la soluzione 
migliore ma perché questo è un tipico esercizio sulla ricorsione... caso 
base... caso passo... solite robe :-)
Alex.

 ha scritto nel messaggio
news:44a63fd6$0$5089$4faf...@reader2.news.tin.it...


> migliore ma perché questo č un tipico esercizio sulla ricorsione... caso


>>Il tuo professore all'uni, ti chiede di risolvere questo problema, te che
fai lo mandi a quel paese dicendo che sia una cazzata, o che non ha
senso???Oppure cerchi di capire come fare per trovare una risposta e quindi
una soluzione????
---
allora, non c'č nessuna risposta e nessuna soluzione da trovare,
l'algoritmo, per come funziona, tiene traccia degli indici per fatti suoi,
senza che tu faccia un bel niente, e alla fine hai il tuo bel indice pronto,
che tu abbia trovato l'elemento o no non cambia una cippa... ora hai capito
perchč era banale la domanda (e la risposta)?
piů di cosě non so che dirti... -_-

 l'elemento, punto e basta.
Con l'algoritmo di ricerca binaria non trovi in nesun caso -1, ma trovi
puittosto senza fare nulla di specile o la posizione in cui si trova,
oppure direttamente la posizione in cui si dovrebbe trovare.
Questa tuaermazione fa capire che non conosci l'algoritmo di ricerca
binaria.
Se poi fai una domanda stupida, ti aiutono spiegandoti che l'algoritmo
di ricerca binaria gia' di per se fa quello che chiedi senza fare
nessuna modifica e ti spiega gentilmente come funziona l'algoritmo di
ricerca binaria, e tu rispondi in questo modo non fai altro che
riiiiiiidicollizarti

Applica dei panni alle tue mani: durante l'arrampicata potrai pulire i 
miei specchi.
P.S: Mi auguro che non sia un corso di Laurea in Ingegneria Informatica, 
perchè in quel caso mi vergognerei.
Mi scuso per l'assenza di quoting, ma non c'era nulla da prendere.
-- 
Emanuele Torrenti
http://torrenti.altervista.org

MeSo ha scritto:
Non hai capito niente.

 basta.
Queste due affermazioni si escludono a vicenda.
-- 
Giambo - Occhio al filtro antispam _e_ alla whitelist !

Ragazzi lasciate stare, ho risolto da solo !!!
Giuseppe Valerio scusami se sono stato scortese con te non volevo,spero che 
mi perdonerai :D e cmq ti ringrazio dell'aiuto! 

 ha scritto nel messaggio
news:44a819f9$0$3120$4faf...@reader1.news.tin.it...

no problem ^_^'