Ricerca binaria
La ricerca binaria si applica agli array ordinati.
Essa controlla se l'elemento richiesto si trova nella posizione centrale dell'array altrimenti concentra la ricerca nella parte
- BASSA se ha trovato un elemento MAGGIORE
- ALTA se ha trovato un elemento MINORE
- non trova l'elemento,
- oppure rimane da esaminare un sottoarray vuoto.
FUNZIONE binaria(IN REALE v[], IN REALE k): INTERO
INIZIO
INTERO risp=-1,
inf=0,
sup=v.QUANTI-1,
medio
MENTRE(inf <= sup AND risp == -1)
INIZIO
medio=(inf+sup)/2
SE(v[medio] < k) ALLORA
inf=medio+1
ALTRIMENTI SE(v[medio] == k) ALLORA
risp=medio
ALTRIMENTI
sup=medio-1
FINE
binaria=risp
FINE
INIZIO
INTERO risp=-1,
inf=0,
sup=v.QUANTI-1,
medio
MENTRE(inf <= sup AND risp == -1)
INIZIO
medio=(inf+sup)/2
SE(v[medio] < k) ALLORA
inf=medio+1
ALTRIMENTI SE(v[medio] == k) ALLORA
risp=medio
ALTRIMENTI
sup=medio-1
FINE
binaria=risp
FINE
Esempio
Sia v=(10.1, 20.2, 30.0, 40.5, 41.1, 42.5, 60)
k = 40.5
- inf=0, sup=6
medio=3
v[3]=40.5 (= k)
binaria=3
- inf=0, sup=6
medio=3
v[3]=40.5 (> k) - inf=0, sup=2
medio=1
v[1]=20.2 (= k)
binaria=1
- inf=0, sup=6
medio=3
v[3]=40.5 (> k) - inf=0, sup=2
medio=1
v[1]=20.2 (> k) - inf=0, sup=0
medio=0
v[0]=10.1 (< k) - inf=1, sup=0
binaria=-1
