La ricerca lineare di 2 miliardi di numeri sarà dolorosa. In media, analizzerete quasi un miliardo di numeri prima di trovare quello che volete. Anche se i numeri sono in memoria, ci vuole un po 'di tempo.
Un approccio migliore consiste nell'ordinare quei numeri mentre li carichi in memoria e quindi utilizzare un algoritmo Ricerca binaria per velocizzare trova il numero desiderato in O (log n) ora.
Non ripeterò qui l'eccellente algoritmo di Wikipedia dell'algoritmo, ma l'idea generale è di campionare il centro dell'elenco e confrontarlo con il numero che stai cercando. Se il tuo numero è più alto, puoi immediatamente scartare la metà più piccola dell'elenco e riprovare con ciò che è rimasto.
- Il tuo primo campione potrebbe trovare il numero o eliminare 1 miliardo di numeri.
- Il tuo secondo campione potrebbe trovare il numero o eliminare 500 milioni di numeri
- Il tuo terzo campione potrebbe trovare il numero o ridurre la ricerca impostata su 250 milioni di numeri.
... e così via. Come puoi vedere, questo converge su una soluzione (o il numero è stato trovato o sai che non è lì) molto rapidamente. C'è un sovraccarico nell'ordinare inizialmente i numeri, ma sono le noccioline rispetto al tempo che salverete nella ricerca.
Se riesci a memorizzare i numeri sul disco ordinato, sarai anche molto più avanti al gioco.