Im che cerca un modo per implementare un codice in Java che funziona allo stesso modo di una ricerca binaria in un ArrayList ordinata ma per una lista ordinata GrazieLa ricerca binaria in un elenco ordinato in java
L'algoritmo dovrebbe essere lo stesso per entrambi uno ArrayList e uno List, dato che sono entrambi ordinati.
È inoltre necessario ricordare che non è possibile eseguire la ricerca binaria se l'elenco non è ordinato. Non ha senso. La ricerca binaria è O(log n) perché puoi in ogni momento ignorare la metà della lista poiché hai la certezza che è stata ordinata. Se la lista non è ordinata, la tua ricerca è O (n) e non puoi usare binari.
una propria implementazione per la ricerca binaria dovrebbe essere simile a questo:
int binary_search(int A[], int key, int imin, int imax)
{
// test if array is empty
if (imax < imin)
// set is empty, so return value showing not found
return KEY_NOT_FOUND;
else
{
// calculate midpoint to cut set in half
int imid = midpoint(imin, imax);
// three-way comparison
if (A[imid] > key)
// key is in lower subset
return binary_search(A, key, imin, imid-1);
else if (A[imid] < key)
// key is in upper subset
return binary_search(A, key, imid+1, imax);
else
// key has been found
return imid;
}
}
fonte: Wikipedia
Se si vuole usare l'esecuzione java.util quindi utilizzare:
java.util.Arrays.binarySearch(int[] a, int key)
Array a dovrebbe essere ordinato naturalmente.
Penso che lo abbia ricordato, ecco perché ha usato la parola "ordinato" nella sua domanda ... – ajb
allora qual è la differenza tra List e ArrayList? vuol dire array ordinato contro arraylist? –
Un ArrayList è un'implementazione di un elenco. Una lista è una sequenza di elementi. Un ArrayList è un modo per rappresentare quegli elementi. LinkedList è un altro. Penso che ArrayList mantenga gli elementi in una struttura a forma di array, in modo che l'accesso a un elemento in qualsiasi indice particolare sia veloce, ma alcune operazioni come l'inserimento nel mezzo dell'elenco sono più lente. LinkedList rende più veloce l'inserimento nel mezzo ma più lento per ottenere l'ennesimo elemento della lista. Nessuno di questi dice nulla sul fatto che gli elementi siano ordinati. – ajb
"Ricerca binaria" ha senso solo se gli elementi della lista (o qualche tipo di puntatori agli elementi) sono organizzati sequenzialmente in memoria, in modo che se si sa che la ricerca è stata ristretta agli indici Low e High, puoi saltare direttamente all'elemento a (Basso + Alto)/2 senza dover attraversare tutti gli altri elementi. Questo non funzionerà per un elenco generale, che potrebbe essere una lista collegata. Per qualcosa del genere, non si può davvero fare meglio di iniziare in cima alla lista e passare attraverso tutti gli elementi in ordine.
È possibile utilizzare
Collections.<T>binarySearch(List<T> list, T key)
per la ricerca binaria su qualsiasi List. Funziona su ArrayList e su LinkedList e su qualsiasi altro List.
Tuttavia:
ricerca binaria è solo veloce se si ha accesso diretto a ogni elemento:
Questo metodo viene eseguito in log (n) per una lista "accesso casuale" (che fornisce vicino -accesso posizionale costante). Se l'elenco specificato non implementa l'interfaccia RandomAccess ed è di grandi dimensioni, questo metodo eseguirà una ricerca binaria basata su iteratore che esegue gli attraversamenti di collegamento O (n) e confronti di elementi O (log n).
Se il List non fornisce "accesso casuale" si potrebbe avere più fortuna con la creazione di una copia di tale List che fa fornire questo.
LinkedList<String> list = new LinkedList<String>();
// fill
O in questo modo
ArrayList<String> fastList = new ArrayList<String>(list);
Collections.binarySearch(fastList, "Hello World");
o forse in questo modo
String[] array = list.toArray(new String[list.size()]);
Arrays.binarySearch(array, "Hello World");
Se il List non è ordinato per impostazione predefinita e si deve risolvere la prima ricerca si potrebbe ottenere il meglio risultato eseguendolo con gli array dal
Collections.sort(list);
crea un array temporaneo che viene ordinato e utilizzato per ricreare l'elenco che dovresti essere in grado di prevenire se lo fai direttamente con gli array.
String[] array = list.toArray(new String[list.size()]);
Arrays.sort(array);
Arrays.binarySearch(array, "Hello World");
ci sono belle classi di utilità con nomi promettenti come 'Collections.binarySearch()' o 'Arrays.binarySearch()' che vengono con ogni Java. – zapl
Salve, se ottieni un downvotes sarà perché non ti stai sforzando, dovresti provare ad affrontare il problema prima di pubblicare una domanda. – jsedano
Questo non ha molto senso. Una lista non è una struttura dati che consente un accesso casuale, non è possibile effettuare una ricerca binaria senza di essa. – piokuc