Java implementiert die binäre Suche

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!