Perché binarySearch su un elenco in Java?

Question

Non sono sicuro del perché List come una struttura di dati generale dovrebbe avere un algoritmo di ricerca binaria dato che l'elenco è ordinato. Non è il metodo get che accetta l'indice attraversa la lista in modo sequenziale, almeno per il sottotipo ? LinkedList? In tal caso, non vedo alcun vantaggio nell'utilizzare binarySearch confrontando con il confronto sequenziale per LinkedList. Ovviamente, a meno che non limitiamo List a ArrayList, possiamo fare binarySearch con maggiore sicurezza.

La mia comprensione è corretta? Grazie.

Answer 1

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!

Answer 2

Sì, hai ragione, se un elenco non fornisce accesso casuale, come nel caso di LinkedList, non c'è alcun vantaggio. Dal javadoc di Collections.binarySearch():

Questo metodo viene eseguito in log (n) per una lista "accesso casuale" (che fornisce quasi costante accesso in tempo posizionale). Se l'elenco specificato non implementa l'interfaccia {@link RandomAccess} ed è di grandi dimensioni, questo metodo eseguirà una ricerca binaria basata su iteratore che esegue gli attraversamenti di link O (n) e confronti di elementi O (log n).

Quindi, la complessità in questo caso sarà la stessa come nel caso di confronto sequenziale - O (n). Praticamente, credo che il confronto sequenziale potrebbe essere più veloce in molti casi.