Ich verwende die Methode binarySearch (), um die Position eines Elements in der Liste zu ermitteln. Und ich verstehe nicht, warum der Index -6 ist. Ich sehe, dass sich das Element nach dem Sortieren in absteigender Reihenfolge an Position 1 befindet. Kann mir jemand sagen, warum ich die Position -6 sehe? Vielen Dank!

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Test
{
    public static void main(String[] args)
    {
        List<Integer> al = new ArrayList<>();
        al.add(100);
        al.add(30);
        al.add(10);
        al.add(2);
        al.add(50);

        Collections.sort(al, Collections.reverseOrder()); 
        System.out.println(al);

        int index = Collections.binarySearch(al, 50);

        System.out.println("Found at index " + index);
    }
}

Die Ausgabe ist: [100, 50, 30, 10, 2]

Gefunden bei Index -6

6
user9608350 19 Apr. 2018 im 13:20

4 Antworten

Beste Antwort

Die Liste muss in aufsteigender natürlicher Reihenfolge angeordnet werden, da sonst die Ergebnisse nicht vorhersehbar sind.

Aus dem Javadoc

Durchsucht die angegebene Liste nach dem angegebenen Objekt mithilfe der Binärdatei Suchalgorithmus. Die Liste muss in aufsteigender Reihenfolge sortiert sein nach der natürlichen Reihenfolge seiner Elemente (wie durch die sort (java.util.List) -Methode) vor diesem Aufruf. Wenn es das nicht ist sortiert sind die Ergebnisse undefiniert . Wenn die Liste mehrere enthält Elemente gleich dem angegebenen Objekt gibt es keine Garantie welche einer wird gefunden.


Wenn Sie nun wirklich wissen möchten, warum das Ergebnis -6 ist, müssen Sie wissen, wie die Methode intern funktioniert. Es nimmt den mittleren Index und prüft, ob er größer oder kleiner als der gesuchte Wert ist.

Wenn es größer ist (was hier der Fall ist), dauert es die zweite Hälfte und führt die gleiche Berechnung durch (niedrig wird mittel und max bleibt max).

Wenn der Schlüssel nicht gefunden wird, gibt die Methode am Ende -(low + 1) zurück, in Ihrem Fall -(5 + 1), da der maximale Index niedrig wird, wenn es keine Möglichkeit gibt, ihn weiter aufzuteilen.

7
Yassin Hajaj 19 Apr. 2018 im 10:29

Abgesehen von der Notwendigkeit, die Liste zu sortieren, binäre Suche

Gibt den Index des Suchschlüssels zurück, falls dieser in der Liste enthalten ist. andernfalls (- (Einfügemarke) - 1)

(Javadoc)

Dh ein negativer Index bezeichnet das Negativ des Index, bei dem das gesuchte Element platziert würde, wenn es vorhanden wäre, minus 1.

Das heißt,

-1 bedeutet, dass es am Index 0 platziert wird

-6 bedeutet, dass es bei Index 5 platziert wird.

3
daniu 19 Apr. 2018 im 20:57

Sie müssen entweder in aufsteigender Reihenfolge sortieren (gemäß der Dokumentation von Collections.binarySearch) oder den benutzerdefinierten Komparator als dritten Parameter übergeben.

int index = Collections.binarySearch(al, 50, Collections.reverseOrder());

Andernfalls wird undefinierte Ergebnisse.

3
Yassin Hajaj 29 Okt. 2019 im 16:16

Ja, aufsteigende Reihenfolge ist für diesen Algorithmus wichtig. Ersetzen Sie einfach die Sortierung durch Collections.sort(al).

Als Ergebnisse haben Sie:

[2, 10, 30, 50, 100]
Found at index 3
0
oleg.cherednik 19 Apr. 2018 im 10:45