Javascript: ricerca binaria negli array



La ricerca binaria si effettua suddividendo l'array in pezzi sempre più piccoli fino a quando non si trova il valore desiderato, a differenza della ricerca sequenziale implementata da indexOf  che scorre l'array da sinistra a destra in una semplice iterazione.

L'operazione deve essere effettuata su un array ordinato, e mediamente utilizza meno confronti rispetto alla ricerca sequenziale, portando a termine la ricerca in meno tempo.




Per quanto riguarda le prestazioni, cito Wikipedia:
La ricerca binaria non usa mai più di (logaritmo base 2 di N approssimato per eccesso) confronti per una search hit o una search miss. Tuttavia, a meno che non si controllino ad ogni iterazione i valori dei due indici estremi, la ricerca binaria impiega effettivamente sempre lo stesso tempo su uno stesso array per cercare elementi anche in posizioni diverse; la ricerca sequenziale invece passa da O(n) come caso peggiore a O(n/2) nel caso medio, fino a O(1) se l'elemento si trova in prima posizione.


Nel semplice demo che ho realizzato, ho esteso la classe Array aggiungendo il metodo binaryIndexOf:


Published: June 27 2013

  • category: