Was ist binäre Suche:
Biometrische Suche ist eine binäre Suche, die nach dem angegebenen Element in einer geordneten Reihenfolge sucht und dabei den Mindestindex (niedrig) und The festlegt Maximaler Index (Höhe-1) und der Zwischenwert Mitte ((niedrig+höhe-1)/2). ist größer als das angegebene Element, Let height=mid-1;
Code-Implementierung: (Kostenlose Video-Tutorial-Freigabe: Java-Video-Tutorial)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int arr[] = { 2, 5, 6, 8, 9, 4, 7 };
Arrays.sort(arr);
int deix（索引） = getxiabiao(arr, 7);
}
public static int getxiabiao(int[] arr, int key) {
int heigh = arr.length-1;
int low = 0;
int mid = 0;
while (low <= heigh) {
mid = low + (heigh - low)/2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
low = mid + 1;
} else if (arr[mid] > key) {
heigh = mid - 1;
}
}
return -1;
}
}Es gibt zwei Möglichkeiten um den Zwischenwert festzulegen;
Algorithmus 1: mittel = (niedrig + hoch) / 2
Algorithmus 2: mittel = niedrig + (hoch – niedrig)/2
Auf den ersten Blick ist Algorithmus 1 einfach, nach der Extraktion durch Algorithmus 2 gibt es keinen Unterschied zu Algorithmus 1. Aber tatsächlich besteht der Unterschied.
Der Ansatz von Algorithmus 1 birgt im Extremfall (niedrig + hoch) das Risiko eines Überlaufs und erhält dann falsche Mittelwerte, was zu Programmfehlern führt, während Algorithmus 2 sicherstellen kann, dass der berechnete Mittelwert sein muss größer als niedrig, kleiner als hoch, es gibt kein Überlaufproblem.
Empfohlene verwandte Artikel und Tutorials: Java-Einführungs-Tutorial
Das obige ist der detaillierte Inhalt vonJava implementiert die binäre Suche. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
