Sammlungen Binäre Suche in Java

1. Grundlegender Algorithmus der binären Suche
2. Syntax von Collections.binarySearch() in Java
3. Arten von Suchen mit Collections.binarySearch() in Java
4. Abschluss

Die Java-Klasse Collections hat eine interne Methode namens binarySearch(), die die Position des Objekts in einer sortierten Liste zurückgibt. Der Parameter der Collections-Funktion binarySearch() ermöglicht eine Unterscheidung nach den verschiedenen Parametern des Skripts.

Der binäre Suchalgorithmus wird von Collections.binarySearch() verwendet, um die mitgelieferte Liste nach dem angeforderten Objekt zu durchsuchen. Vor diesem Aufruf muss die Liste in aufsteigender Reihenfolge sortiert werden, wobei die natürliche Reihenfolge ihrer Elemente verwendet wird.

Wenn es nicht sortiert ist, sind die Ergebnisse nicht klar. Es besteht keine Gewissheit, dass das gewünschte Element gefunden wird, wenn die Liste viele Elemente enthält, die mit dem angeforderten Objekt identisch sind.

Grundlegender Algorithmus der binären Suche

Bei der binären Suche wird die Sammlung immer wieder halbiert. Je nachdem, ob das Schlüsselelement kleiner oder größer als das mittlere Element der Sammlung ist, wird die linke oder rechte Hälfte der Sammlung nach dem Schlüsselelement durchsucht.

Zu befolgende Schritte in einem binären Suchalgorithmus:

1. Bestimmen Sie den Mittelpunkt der Sammlung.
2. Vergleichen Sie das Mittelelement mit den wesentlichen Komponenten.
3. Sie geben die mittlere Indexposition für den gefundenen Schlüssel zurück, wenn der Schlüssel derselbe wie das mittlere Element ist.
4. Andernfalls, wenn der Schlüssel > mittleres Element ist, befindet sich der Schlüssel in der rechten Hälfte der Sammlung. Wiederholen Sie die Schritte 1 bis 3, um die untere (rechte) Hälfte der Sammlung zu vervollständigen.
5. Wenn der Schlüssel ein mittleres Element ist, befindet sich der Schlüssel in der oberen Hälfte der Sammlung. Infolgedessen müssen Sie die binäre Suche in der oberen Hälfte erneut durchführen.

Syntax von Collections.binarySearch() in Java

Die folgende Syntax wird verwendet, um diese Methode zu deklarieren.

public static <T> int binarySearch(List<? extends Comparable<? super T>> list,
    T key) public static <T> int binarySearch(List<? extends T> list, T key,
    Comparator<? super T> c)

Es gibt 2 Arten von Collections.binarySearch()-Methoden:

1. Java Collections binarySearch(List<? extends Comparable<? super T>> list, T key).

   Vor Anwendung des Verfahrens muss die Liste anhand der angegebenen natürlichen Zahl aufsteigend geordnet werden. Die Ergebnisse sind undefinierbar, wenn die Liste nicht sortiert ist.

2. Java Collections binarySearch(List<? extend T> list, T key, Comparator<? super T> c).

   Vor dem Aufruf der Prozedur muss die Liste mit dem mitgelieferten Komparator aufsteigend sortiert werden.

Arten von Suchen mit Collections.binarySearch() in Java

Damit binarySearch() wie beabsichtigt funktioniert, müssen Ihre Daten durch den bereitgestellten Komparator geordnet werden. Vor diesem Aufruf muss die Liste mit dem mitgelieferten Vergleicher aufsteigend sortiert werden.

Die Prozedur liefert den Index des gesuchten Elements, wenn die Daten sortiert sind; Andernfalls wird (-(Einfügepunkt) - 1) zurückgegeben.

Suchen Sie einen ganzzahligen Schlüssel in einer aufsteigend geordneten Liste.

Beispielcode:

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

public class Main {
  public static void main(String[] args) {
    List<Integer> al = new ArrayList<Integer>();
    al.add(3);
    al.add(4);
    al.add(5);
    al.add(20);
    al.add(30);

    int index = Collections.binarySearch(al, 20);
    System.out.println(index);

    index = Collections.binarySearch(al, 12);
    System.out.println(index);
  }
}

Ausgang:

3
-4

Suchen Sie einen ganzzahligen Schlüssel in einer absteigend geordneten Liste.

Beispielcode:

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

public class Main {
  public static void main(String[] args) {
    List<Integer> al = new ArrayList<Integer>();
    al.add(350);
    al.add(90);
    al.add(45);
    al.add(20);
    al.add(3);

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

    System.out.println(index);
  }
}

Ausgang:

2

Abschluss

Die Sammlungen binarySearch() ist die beliebteste Suchmethode. Voraussetzung ist hier, dass die Daten aufsteigend sortiert sein müssen, damit eine binäre Suche erfolgreich ist.

Sowohl iterative als auch rekursive Verfahren können verwendet werden, um eine binäre Suche zu implementieren. Die Java-Klasse Arrays bietet zusätzlich die Methode binarySearch(), die eine binäre Suche auf einem Array durchführt.