Wie implementiert man die binäre Suche in Java?

Es gibt zwei Möglichkeiten, eine binäre Suche in Java durchzuführen.

1.Arrays.binarysearch()Gilt für Arrays, die auch primitive Datentypen sein können.

import java.util.Arrays; 
  
public class GFG { 
    public static void main(String[] args) 
    { 
        int arr[] = { 10, 20, 15, 22, 35 }; 
        Arrays.sort(arr); 
  
        int key = 22; 
        int res = Arrays.binarySearch(arr, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
  
        key = 40; 
        res = Arrays.binarySearch(arr, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
    } 
}

Ausgabe:

22 found at index = 3
40 Not found

2.Collections.binarysearch()Gilt für Objektsammlungen wie ArrayList und LinkedList.

import java.util.List; 
import java.util.ArrayList; 
import java.util.Collections; 
   
public class GFG 
{ 
    public static void main(String[] args) 
    { 
        List<Integer> al = new ArrayList<Integer>(); 
        al.add(1); 
        al.add(2); 
        al.add(3); 
        al.add(10); 
        al.add(20); 
   
        int key = 10; 
        int res = Collections.binarySearch(al, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                 + res); 
        else
            System.out.println(key + " Not found"); 
  
        key = 15; 
        res = Collections.binarySearch(al, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = "
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
    } 
}

Ausgabe:

10 found at index = 3
15 Not found

Was passiert, wenn die Eingabe nicht sortiert ist?
Wenn die Eingabeliste nicht sortiert ist, ist das Ergebnis undefiniert.

Was passiert, wenn es Duplikate gibt?
Wenn es Duplikate gibt, gibt es keine Garantie, welches gefunden wird.

Wie funktioniert Collections.binarySearch für LinkedList?
Diese Methode läuft in Log(n)-Zeit und wird für Listen mit „wahlfreiem Zugriff“ wie ArrayList verwendet. Wenn die angegebene Liste die RandomAccess-Schnittstelle nicht implementiert und groß ist, führt diese Methode eine iteratorbasierte binäre Suche durch, die eine O(n)-Linkdurchquerung und einen O(log n)-Elementvergleich durchführt.

Welche Bedeutung haben die von den beiden Funktionen zurückgegebenen negativen Werte?
Diese Funktion gibt den Index des Suchschlüssels zurück (sofern er im Array enthalten ist); andernfalls (- (Einfügepunkt) - 1). Der Einfügepunkt ist als der Punkt definiert, an dem der Schlüssel in das Array eingefügt wird: Der Index des ersten Elements ist größer als der Schlüssel oder a.length, wenn alle Elemente im Array kleiner als der angegebene Schlüssel sind. Beachten Sie, dass dies genau dann einen Rückgabewert >= 0 garantiert, wenn der Schlüssel gefunden wird.

Wie implementiert man unsere eigene binäre Suche in Java?

class BinarySearch 
{ 
    int binarySearch(int arr[], int l, int r, int x) 
    { 
        if (r>=l) 
        { 
            int mid = l + (r - l)/2; 
            if (arr[mid] == x) 
               return mid; 

            if (arr[mid] > x) 
               return binarySearch(arr, l, mid-1, x); 
 
            return binarySearch(arr, mid+1, r, x); 
        } 

        return -1; 
    } 
 
    public static void main(String args[]) 
    { 
        BinarySearch ob = new BinarySearch(); 
        int arr[] = {2,3,4,10,40}; 
        int n = arr.length; 
        int x = 10; 
        int result = ob.binarySearch(arr,0,n-1,x); 
        if (result == -1) 
            System.out.println("Element not present"); 
        else
            System.out.println("Element found at index " +  
                                                 result); 
    } 
}

Ausgabe:

Element found at index 3

Verwandte Empfehlungen: „Java-Tutorial“

Dieser Artikel ist eine Einführung in die Methode zur Implementierung der binären Suche in Java, ich hoffe, es wird Freunden in Not hilfreich sein!

Das obige ist der detaillierte Inhalt vonWie implementiert man die binäre Suche in Java?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!