Ricerca binaria in un elenco ordinato in java

Im in cerca di un modo per implementare un codice in java che funziona allo stesso modo come una ricerca binaria in un insieme ordinato ArrayList, ma per un Elenco ordinato
Grazie

ci sono classi di utilità promettenti nomi come Collections.binarySearch() o Arrays.binarySearch() di Java.
Ciao, se ti downvotes sarà perché si stanno mostrando alcun sforzo, si dovrebbe cercare di affrontare il problema prima di postare una domanda.
Che in realtà non ha molto senso. L’Elenco non è una struttura di dati, consentendo un accesso casuale, non si può davvero fare una ricerca binaria senza che.
L’elenco non è una struttura di dati, consentendo l’accesso casuale? Sì, lo è.

InformationsquelleAutor JsMartinez | 2013-08-07

4 Replies
  1. 1

    L’algoritmo dovrebbe essere la stessa sia per un ArrayList e un List, dato che entrambi sono ordinati.

    InformationsquelleAutor gr3co

  2. 20

    È possibile utilizzare

    Collezioni.<T>binarySearch(Lista<T> elenco, tasto T)

    per la ricerca binaria su qualsiasi List. Funziona su ArrayList e LinkedList e su qualsiasi altro List.

    Tuttavia:

    binario di ricerca è veloce solo se si dispone di accesso diretto per ogni elemento:

    Questo metodo viene eseguito nel log(n) tempo di accesso casuale (random access list (che fornisce vicino-costante di tempo posizionale di accesso). Se l’elenco specificato di non implementare il RandomAccess interfaccia ed è di grandi dimensioni, questo metodo di fare un iteratore basato su binari di ricerca che esegue O(n) link attraversamenti e O(log n) elemento di confronto.

    Se il tuo List non fornisce “accesso casuale” si potrebbe avere più fortuna con la creazione di una copia di tale List che questo.

    LinkedList<String> list = new LinkedList<String>();
    //fill

    Sia come

    ArrayList<String> fastList = new ArrayList<String>(list);
    Collections.binarySearch(fastList, "Hello World");

    o forse come

    String[] array = list.toArray(new String[list.size()]);
    Arrays.binarySearch(array, "Hello World");

    Se il tuo List non è ordinato per impostazione predefinita e si deve risolvere prima la ricerca, si potrebbe ottenere il risultato migliore da fare con le matrici dal

    Collections.sort(list);

    crea un array temporaneo ordinati e ri-creare la lista che si dovrebbe essere in grado di evitare che se la fai con le matrici direttamente.

    String[] array = list.toArray(new String[list.size()]);
    Arrays.sort(array);
    Arrays.binarySearch(array, "Hello World");

    InformationsquelleAutor zapl

  3. 1

    “Ricerca binaria” ha senso solo se gli elementi della lista (o un qualche tipo di puntatori agli elementi) sono organizzati in sequenza in memoria, in modo che se sanno che la ricerca è stata ridotta a indici di Bassa e Alta, si può saltare a destra per l’elemento a (Basso + Alto) /2 senza dover sgobbare attraverso tutti gli altri elementi. Questo non è andare a lavorare per un Elenco generale, che potrebbe essere una LinkedList. Per qualcosa di simile, si può davvero fare di meglio che partire in testa alla lista e passare attraverso tutti gli elementi in ordine.

    InformationsquelleAutor ajb

  4. 0

    Si dovrebbe anche ricordare che non si può fare la ricerca binaria se la lista non è ordinata. Non ha senso. Ricerca binaria è O(log n) perché è possibile in ogni punto di ignorare metà della lista in quanto è a conoscenza del fatto che si è ordinato. Se la lista non è ordinata, allora la vostra ricerca è O(n) e non è possibile utilizzare il binario.

    implementazione per la ricerca binaria dovrebbe assomigliare a questa:

    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 desidera utilizzare Java.util attuazione usare:

    java.util.Arrays.binarySearch(int[] a, int key)

    Array a deve essere ordinato di corso.

    Penso che abbia fatto ricordare che, per questo ha usato la parola “ordine” nella sua domanda…
    quindi qual è la differenza tra Lista e ArrayList? significa matrice ordinata vs arraylist?
    Un ArrayList è una implementazione di una Lista. Una Lista è una sequenza di elementi. Un ArrayList è un modo per rappresentare gli elementi. LinkedList è un altro. Penso ArrayList mantiene gli elementi in un array di struttura, in modo che l’accesso a un elemento in un particolare indice è più rapido, ma alcune operazioni come l’inserimento nel mezzo della lista sono più lenti. LinkedList rende più veloce l’inserimento nel mezzo, ma più lento per ottenere l’n-Esimo elemento della lista. Nessuno di quelli che dicono nulla se gli elementi sono ordinati.
    sì, lo so. L’elenco è un’interfaccia. Così forse lui intendeva array vs arrayList

    InformationsquelleAutor Saher Ahwal

Lascia un commento