So implementieren Sie einen binären Suchalgorithmus mit Java

So implementieren Sie einen binären Suchalgorithmus in Java

Der binäre Suchalgorithmus ist eine effiziente Suchmethode, die für sortierte Arrays geeignet ist. Seine Grundidee besteht darin, den Suchbereich kontinuierlich einzuschränken, den Suchwert mit den Elementen in der Mitte des Arrays zu vergleichen und basierend auf dem Vergleichsergebnis zu entscheiden, ob die Suche in der linken oder rechten Hälfte fortgesetzt werden soll, bis das Zielelement gefunden wird oder Der Suchbereich wird auf leer reduziert.

Jetzt stellen wir detailliert vor, wie der binäre Suchalgorithmus in Java implementiert wird.

Schritt 1: Implementieren Sie die binäre Suchmethode

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1; //表示未找到目标元素
    }
}

Schritt 2: Testen Sie die binäre Suchmethode

public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}; //已排序数组
        int target = 12; //要查找的目标元素
        int index = BinarySearch.binarySearch(arr, target);
        
        if (index != -1) {
            System.out.println("目标元素在数组中的位置为：" + index);
        } else {
            System.out.println("未找到目标元素");
        }
    }
}

Der obige Code definiert zunächst eine BinarySearch-Klasse, die eine statische Methode binarySearch wird verwendet, um den binären Suchalgorithmus zu implementieren. In der Methode <code>binarySearch definieren wir zwei Zeiger, left und right, um auf die Elemente ganz links bzw. ganz rechts im Suchbereich zu zeigen. In einer Schleife wird der Index des mittleren Elements mid berechnet und anschließend der Lookup-Wert mit arr[mid] verglichen. Wenn beide gleich sind, bedeutet dies, dass das Zielelement gefunden wurde und sein Indexwert mid zurückgegeben wird. Wenn der Suchwert größer als arr[mid] ist, bewegen Sie den Zeiger links um eine Position nach rechts und schränken Sie den Suchbereich auf die rechte Hälfte ein. Wenn der Suchwert kleiner als arr[mid] ist, bewegen Sie den Zeiger rechts um eine Position nach links, um den Suchbereich auf die linke Hälfte einzugrenzen. Die Schleife wird fortgesetzt, bis das Zielelement gefunden wird oder der Suchbereich leer ist. Wenn das Zielelement nach Ende der Schleife nicht gefunden wird, wird -1 zurückgegeben, um anzuzeigen, dass es nicht gefunden wurde. BinarySearch类，其中包含了一个静态方法binarySearch用于实现二分查找算法。在binarySearch方法中，我们定义了left和right两个指针分别指向查找范围的最左和最右元素。在一个循环中，通过计算得到中间元素的索引mid，然后将查找值与arr[mid]进行比较。如果两者相等，则表示找到了目标元素，返回其索引值mid。如果查找值大于arr[mid]，则将left指针右移一位，缩小查找范围为右半部分。如果查找值小于arr[mid]，则将right指针左移一位，缩小查找范围为左半部分。循环继续直到找到目标元素或查找范围为空。如果循环结束后未找到目标元素，返回-1表示未找到。

在Main类的main方法中，我们创建了一个已排序的数组arr和一个待查找的目标元素target。然后调用BinarySearch类的binarySearch方法进行二分查找，将返回的结果存储在index

In der Methode main der Klasse Main erstellen wir ein sortiertes Array arr und ein zu findendes Zielelement target. Rufen Sie dann die Methode <code>binarySearch der Klasse BinarySearch auf, um eine binäre Suche durchzuführen, und speichern Sie das zurückgegebene Ergebnis in der Variablen index. Abschließend wird anhand des zurückgegebenen Ergebnisses beurteilt, ob das Zielelement gefunden wurde, und das entsprechende Ergebnis wird gedruckt.

Anhand der obigen Codebeispiele können wir sehen, dass die Implementierung des binären Suchalgorithmus in Java sehr einfach ist und nur wenige Codezeilen erfordert. Diese Methode hat eine Suchzeitkomplexität von O(logn), was sehr effizient und für große sortierte Arrays geeignet ist. Wenn mehrere Suchvorgänge erforderlich sind, kann der Sortiervorgang des Arrays zur Verbesserung der Effizienz separat aufgeteilt werden.

Ich hoffe, dieser Artikel hilft Ihnen, den binären Suchalgorithmus zu verstehen und zu verwenden! 🎜

Das obige ist der detaillierte Inhalt vonSo implementieren Sie einen binären Suchalgorithmus mit Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!