Binary wyszukiwania w uporządkowanej listy w java

Question

Im szuka sposobu, aby zrealizować kod w Javie, który działa w ten sam sposób jak binarnego wyszukiwania w uporządkowanej ArrayList ale uporządkowaną listę Dzięki

Answer 1

Algorytm powinien być to samo dotyczy zarówno modelu ArrayList, jak i List, ponieważ oba są uporządkowane.

Answer 2

Należy również pamiętać, że nie można wykonywać wyszukiwania binarnego, jeśli lista nie została zamówiona. To nie ma sensu. Wyszukiwanie binarne to O(log n), ponieważ możesz w każdym miejscu pominąć połowę listy, ponieważ wiesz, że jest ona uporządkowana. Jeśli lista nie jest uporządkowana, twoje wyszukiwanie to O (n) i nie możesz użyć binarnego.

własne wdrożenie do poszukiwań binarnych powinna wyglądać następująco:

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; 
    } 
} 

źródło: Wikipedia

Jeśli chcesz użyć realizację java.util następnie użyć:

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

Array a należy oczywiście posortować.

Answer 3

"Wyszukiwanie binarne" ma sens tylko wtedy, gdy elementy listy (lub jakiś rodzaj wskaźników do elementów) są porządkowane w pamięci, tak aby wiedzieć, że wyszukiwanie zostało zawężone do indeksów Niski i Wysoki, możesz przeskoczyć w prawo do elementu na poziomie (Low + High)/2, bez konieczności przepychania się przez wszystkie inne elementy. To nie będzie działać dla ogólnej Listy, która może być Listą Powiązaną. W przypadku czegoś takiego nie można zrobić nic lepszego, niż zacząć od początku listy i przeglądać wszystkie elementy w kolejności.

Answer 4

Można użyć

Collections.<T>binarySearch(List<T> list, T key)

dla wyszukiwania binarnego na każdym List. Działa na ArrayList i na LinkedList i na każdym innym List.

Jednakże:

wyszukiwania binarny jest tylko szybko, jeśli mają bezpośredni dostęp do każdego elementu:

Ta metoda działa w log (n) dla „random access” listy (która zapewnia pobliżu -terminowy dostęp pozycyjny). Jeśli podana lista nie implementuje interfejsu RandomAccess i jest duża, ta metoda wykona binarne wyszukiwanie oparte na iteratorze, które wykona O (n) przewijanie łączy i porównań elementów O (log n).

Jeśli Twój List nie przewiduje „random access” może mieć więcej szczęścia, tworząc kopię tego List że nie przewiduje tego.

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

Albo jak tak

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

czy może jak tak

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

Jeśli Twój List nie zamówił domyślnie i trzeba posortować je przed poszukiwania można uzyskać najlepsze wynik przez wykonanie z tablicami od

Collections.sort(list); 

tworzy tymczasową tablicę, która jest sortowana i używana do ponownego utworzenia listy, którą powinieneś być w stanie zapobiec, jeśli robisz to bezpośrednio z tablicami.

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