La funzione radice quadrata ha un andamento monotono crescente.
Osserva
Ricerca sequenziale
Una possibile strategia
- Partire dal valore più basso possibile (0 oppure 1)
- Aumentare il valore di un certo passo finché il suo quadrato è inferiore a x
- Annullare l’ultimo aumento
- Diminuire il valore del passo
- Ripetere dal punto 2. finché…
Più formalmente
- Se x < 1 allora y = 0 altrimenti y = 1
- passo = x/10
- y = y + passo
- Se y^2 > x allora
- y = y – passo
- passo = passo / 10
- Continua dal punto 3. finché…
La scelta di partire dal basso e incrementare è ragionevole…
La scelta del valore 10 al cambio di passo è ragionevole…
Ricerca binaria
- Stabilire l’intervallo della soluzione
- Scegliere il valore centrale dell’intervallo
- Se il quadrato del valore è inferiore a x allora la metà inferiore dell’intervallo viene scartata
- Se il quadrato del valore è maggiore di x allora la metà superiore dell’intervallo viene scartata
- Ripetere dal punto 2. finché…
Più formalmente
- Se x < 1 allora l’intervallo è [0, 1] altrimenti [1, x]
- y è uguale al centro dell’intervallo
- Se y^2 < x allora y diventa l’estremo inferiore dell’intervallo: [y, …]
- Se y^2 > x allora y diventa l’estremo superiore dell’intervallo: […, y]
- Continua dal punto 2. finché…
A ogni passo le distanze si dimezzano…