Ricerca di un numero mediante approssimazioni successive

La ricerca di un numero per approssimazioni successive (nota anche come ricerca ordinata o ricerca dicotomica) consente di trovare un numero dato in un numero massimo di passi, pari ai bit utilizzati.

Il numero di bit, massimo consentito è 64 (quindi il numero massimo da cercare è 2⁶⁴ - 1). La ricerca parte dalla metà del valore massimo prefissato e - confrontando questo valore con il numero da cercare - si sposta verso di esso, dimezzando l'intervallo ad ogni step.

La ricerca prosegue finché non incontra il numero dato, restituendo il numero di passi impiegati. Per ottenere una ricerca con un numero di passi pari al massimo possibile (ovvero il numero di bit) è sufficiente inserire un numero dispari.

Infatti, in questo caso, il bit meno significativo (Least Significant Bit) vale 1, ed è l'ultimo bit ad essere determinato.

Invece, durante la ricerca del numero (a seconda che si proceda aumentando o diminuendo il valore precedente) si ottengono gli "0" ed "1" della cifra binaria, eseguendo così - oltre alla ricerca del numero - la sua conversione da decimale a binario.

Nelle note sono disponibili i link per chi non disponesse del FrameWork per l'esecuzione dell'applicativo (scaricabile gratuitamente) e dell'ambiente di sviluppo (in lingua inglese).

Allegati

• Ricerca dicotomica (38 Kb - Formato rar)
  Cristian Clementi
  Applicativo eseguibile per la ricerca di un numero, mediante la tecnica delle approssimazioni successive. Richiede l'ambiente FrameWork .net installato.
  Copyright © Cristian Clementi

  Licenza: CC Attribuzione - Non commerciale - Non opere derivate 3.0

• Ricerca dicotomica (codice sorgente) (46 Kb - Formato rar)
  Cristian Clementi
  La compilazione dei codici sorgenti richiede Visual Studio 2008.
  Copyright © Cristian Clementi

  Licenza: CC Attribuzione - Non commerciale - Non opere derivate 3.0