Veranschaulichung des Prinzips und der Implementierung der binären Suche mit dem klassischen Java-Algorithmus

Dieser Artikel vermittelt Ihnen relevantes Wissen über Java. Die Halbsuchmethode wird auch als binäre Suche bezeichnet. Sie teilt die Daten in zwei Hälften, bestimmt dann, in welcher Hälfte der Schlüssel gefunden wird, und wiederholt dann den oben genannten Vorgang Nachdem Sie nun den Zielschlüssel gefunden haben, werfen wir einen Blick darauf. Ich hoffe, er wird für alle hilfreich sein.

Empfohlenes Lernen: „Java-Video-Tutorial“

Binäre Suche

Die binäre Suche wird auch als binäre Suche (Binary Search) bezeichnet. Es handelt sich um eine effizientere Suchmethode, die im Logarithmus der Daten verwendet werden kann Größe. Schließen Sie die Suche innerhalb der Zeitkomplexität ab. Es handelt sich um einen Suchalgorithmus zum Auffinden eines bestimmten Elements in einem geordneten Array.

Algorithmusidee

Nehmen Sie die aufsteigende Sequenz als Beispiel, vergleichen Sie die Größe des Zielelements und des Elements in der Mitte der Sequenz. Wenn das Zielelement größer als das Element in der Mitte ist, führen Sie weiterhin eine binäre Suche durch in der zweiten Hälfte der Sequenz; wenn das Zielelement kleiner ist als das Element in der mittleren Position, wird der Vergleich in der ersten Hälfte des Arrays durchgeführt, wenn sie gleich sind, wird die Position des Elements gefunden. Die Länge des Arrays für jeden Vergleich beträgt die Hälfte des vorherigen Arrays, bis die Position gleicher Elemente gefunden wird oder das Zielelement nicht gefunden wird.

Abbildung

Gegeben sei ein geordnetes Array in aufsteigender Reihenfolge nums=[-1, 0, 2, 5, 8, 12, 18, 38, 43, 46]

Dann finden Sie den Zielwert target im Array =12.

Das Diagramm sieht wie folgt aus:

In der Nähe der ursprünglichen Frage

Portal

Problembeschreibung:

Bei gegebenen n-Elementen geordneten (aufsteigenden) ganzzahligen Array-Nummern und einem Zielwertziel schreiben Sie eine Suchfunktion für Ziel in Zahlen und geben Sie den Index zurück, wenn der Zielwert vorhanden ist, andernfalls -1.

Beispiel 1:

Eingabe: Nums = [-1,0,3,5,9,12], Ziel = 9
Ausgabe: 4
Erklärung: 9 erscheint in Nums und der Index ist 4

Beispiel 2:

Eingabe: Nums = [-1,0,3,5,9,12], Ziel = 2
Ausgabe: -1
Erklärung: 2 existiert nicht in Nums, daher wird -1 zurückgegeben

Lösung des Problems Idee:

Entsprechend der Bedeutung der Frage kann daraus geschlossen werden, dass es sich bei dem Array um ein geordnetes Array handelt, was auch eine Voraussetzung für die Verwendung der binären Suche ist.

• Definieren Sie zwei Zeiger, die auf das erste und letzte Element des Arrays zeigen.
• Finden Sie den mittleren Wert in der Mitte des Arrays.
• Wenn nums[mid] < befindet sich in der zweiten Hälfte des Array-Teils, andernfalls befindet sich <code>nums[mid] > target in der ersten Hälfte. nums[mid] < target，则 target 位于数组的后半部分，反之nums[mid] > target在前半部分；
• 重复上一步操作，直到nums[mid] = target
Wiederholen Sie den vorherigen Schritt, bis nums[mid] = target; Code>, der angibt, dass das Ziel gefunden und der Index zurückgegeben wird. Das war's.

Java-Code-Implementierung:

class Solution {
    public int search(int[] nums, int target) {
        int left = 0,right = nums.length - 1;
        while(left <= right) { // 循环条件
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;  // 找不到则返回-1
    }
}

Komplexitätsanalyse:

• Zeitliche Komplexität: O(logn), wobei n die Länge des Arrays ist.
• Raumkomplexität: O(1).

Empfohlenes Lernen: „Java-Video-Tutorial

“🎜

Das obige ist der detaillierte Inhalt vonVeranschaulichung des Prinzips und der Implementierung der binären Suche mit dem klassischen Java-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!