So implementieren Sie die Iteration in der Java-Binärsuche
- WBOYnach vorne
- 2023-05-29 20:33:01985Durchsuche
1. Konzept der Iteration
Die wiederholte Ausführung einer Reihe von Anweisungen oder bestimmter Schritte wird als Iteration bezeichnet. Um es für Laien auszudrücken: Rufen Sie sie einzeln auf.
Dinge, die eine solche Funktion zum Zählen der Vergangenheit implementieren, werden Iteratoren genannt.
2. Drei Elemente der Iteration
1. Bestimmen Sie Variablen
In Problemen, die durch iterative Algorithmen gelöst werden können, gibt es mindestens eine Variable, die direkt oder indirekt kontinuierlich neue Werte aus alten Werten ableitet. Diese Variable ist Iterate-Variablen.
2. Stellen Sie eine Beziehung her
Die sogenannte iterative Beziehung bezieht sich auf die Formel (oder Beziehung), wie der nächste Wert einer Variablen aus ihrem vorherigen Wert abgeleitet wird. Die Herstellung iterativer Beziehungen ist der Schlüssel zur Lösung iterativer Probleme, die normalerweise durch Rekursion oder Rückwärtsschlussfolgerungen gelöst werden können.
3. Prozesskontrolle
Wann sollte der iterative Prozess enden? Dies ist ein Problem, das beim Schreiben eines iterativen Programms berücksichtigt werden muss. Der iterative Prozess kann nicht endlos wiederholt werden. Die Steuerung des iterativen Prozesses kann normalerweise in zwei Situationen unterteilt werden: Zum einen ist die erforderliche Anzahl von Iterationen ein bestimmter Wert und kann berechnet werden. Zum anderen kann die erforderliche Anzahl von Iterationen nicht bestimmt werden. Für den ersteren Fall kann eine feste Anzahl von Schleifen zur Steuerung des iterativen Prozesses erstellt werden; für den letzteren Fall müssen die Bedingungen für die Beendigung des iterativen Prozesses weiter analysiert werden.
3. Iterationsbeispiel einer binären Suche
/*非递归的折半查找*/
public static int binarySearch(int[] a, int x) {
int left = 0;
int right = a.length - 1;
while(left <= right) {
int mid = (left+ right) / 2;
if(x > a[mid]) {
left = mid+1;
} else if(x < a[mid]) {
right = mid-1;
} else {
return mid;
}
}
return -1;
}
Alle Arbeiten innerhalb der Schleife kosten O(1) für jede Iteration, daher muss die Analyse die Anzahl der Schleifen bestimmen. Die Schleife beginnt bei rechts-links=länge-1 und endet bei rechts-links<= -1. Nach jedem Zyklus beträgt der Wert von rechts-links mindestens die Hälfte des Wertes vor dem Zyklus; daher beträgt die maximale Anzahl von Zyklen [log(n-1)]+2. Daher: Die Laufzeit beträgt O(log N), während die rekursive Zeitkomplexität O(N) erfordert.
Das obige ist der detaillierte Inhalt vonSo implementieren Sie die Iteration in der Java-Binärsuche. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!