Esistono molti modi per implementare lo List
. C'è , , CopyOnWriteArrayList
, ecc. Nelle librerie Java standard e una serie di altre implementazioni oltre a quelle (VLists, buffer circolari, elenchi di binomiali obliqua, extendible arrays, 2-3 finger trees, ecc.). L'idea alla base della ricerca binaria è che mentre non tutte le implementazioni di List supportano l'accesso casuale, quelle che trarrebbero vantaggio dall'avere una implementazione generica della ricerca binaria disponibile in modo che gli autori di ciascuna struttura di dati non debbano reimplementarlo da zero. Ad esempio, se implemento una nuova struttura lista pazzesca che supporta l'accesso casuale, se implemento l'interfaccia Elenco, è possibile ottenere automaticamente una ricerca binaria disponibile dalla classe Collections.
È interessante notare che il metodo binarySearch
è scritto in modo tale che si guarda al tipo di List
e vede se si implementa l'interfaccia RandomAccess
prima che effettivamente fa la ricerca binaria. Se l'elenco non implementa RandomAccess
, anziché utilizzare una ricerca binaria standard, il metodo utilizza una ricerca binaria modificata con iteratori che è garantita per eseguire al massimo O (n) iterazioni e O (log n) confronti. L'idea è di tenere traccia di dove l'ultima sonda è atterrato, quindi di camminare avanti o indietro il numero appropriato di passi per trovare la prossima posizione della sonda, ecc. Il lavoro totale svolto è quindi al massimo n/2 + n/4 + n/8 + n/16 + ... = 2n, quindi nel caso peggiore è solo il doppio di una ricerca lineare nel caso peggiore.
In breve, fornire un'implementazione generica di binarySearch
non sempre consente di cercare rapidamente un elenco per qualcosa, ma per le strutture che supportano l'accesso rapido può fare un'enorme differenza e risparmiare molto tempo per l'implementatore . Inoltre, avere il gradevole degrado della ricerca binaria modificata che viene eseguita nel tempo O (n) significa che l'implementazione non sarà mai peggiore di una scansione lineare standard.
Questo ragionamento è simile al ragionamento alla base del progetto degli algoritmi C++, che operano su intervalli di valori generici. L'efficienza di questi algoritmi potrebbe essere molto peggiore di una versione specializzata dell'algoritmo basata su una struttura per-data, ma avere la versione generale disponibile significa che qualsiasi nuovo contenitore che supporta gli iteratori può avere automaticamente molte funzionalità disponibili oltre a ciò che è specificato nell'interfaccia.
Spero che questo aiuti!
"dato l'elenco è ordinato" - non è un dato. –
Sto solo dando per scontato che sia vero. Oppure possiamo sempre ordinarlo prima. –
Hai ragione, fare una ricerca binaria su LinkedList è una cattiva idea. – Seramme