IT-Academy Logo
Sign Up Login Help
Home - Programmieren - Java - Binäre Suche in Java



Binäre Suche in Java

Eine sehr detaillierte Beschreibung und Analyse der binären Suche als rekursiver und iterativer Algorithmus in der Programmiersprache Java.


Autor: Tobias Surmann (incsoft)
Datum: 08-08-2004, 17:52:33
Referenzen: siehe Quellen
Schwierigkeit: Profis
Ansichten: 25603x
Rating: 7.5 (2x bewertet)

Hinweis:

Für den hier dargestellte Inhalt ist nicht der Betreiber der Plattform, sondern der jeweilige Autor verantwortlich.
Falls Sie Missbrauch vermuten, bitten wir Sie, uns unter missbrauch@it-academy.cc zu kontaktieren.

[Druckansicht] [Als E-Mail senden] [Kommentar verfassen]



Einleitung

Eine häufige Problemstellung in der Informatik ist das Wiederauffinden von gesuchten Daten in einem Array. Um solche Daten finden zu können wird ihnen meist ein Schlüssel zugeordnet. Wir werden zur Vereinfachung in diesem Artikel keine Schlüssel für einzelne Datenobjekte definieren, sondern unseren binären Suchalgorithmus so implementieren, dass wir nur mit Schlüsseln (vom Typ int) arbeiten und ohne Datenobjekte auskommen. Denn wir wollen uns ja mit dem eigentlichen Problem des Suchens beschäftigen.

Vorraussetzungen

Ich zeige hier den kompletten Code in Java, also sollten Sie in der Lage sein, Java-Quelltext zu verstehen, um auch diesen Artikel nachvollziehen zu können. Auf einzelne Anweisungen und Programmiertechniken (wie z.B. die Rekursion) werde ich grundsätzlich nicht mehr eingehen, es sei denn, sie haben einen speziellen Bezug zum diskutierten Problem.

Nun zu den Vorraussetzungen, um die binäre Suche überhaupt verwenden können. Dazu müssen die Zahlen bzw. Schlüssel im Array zunächst einmal sortiert sein (in welcher Reihenfolge ist egal, allerdings wird zumeist aufsteigend sortiert). Über Algorithmen, die eine Sortierung bewerkstelligen soll es an dieser Stelle nicht gehen. Wir nehmen also der Einfachheit halber hin, dass unser Array schon sortiert ist. Sollten Sie Interesse an Sortierverfahren haben, so finden Sie hilfreiche Literaturhinweise und Links zum Thema unter Quellen.

Prinzip

Prinzipiell arbeitet die binäre Suche nach dem Teile-und-Herrsche-Prinzip (divide and conquer). Dieses funktioniert folgendermaßen: man hat ein Problem der Größe n. Nun zerteilt man dies in zwei etwa gleich große Teile der gleichen Art. Diese löst man nun wieder auf die gleiche Weise. Diese Vorgehensweise setzt natürlich voraus, dass wir ein Problem der Größe 1 recht einfach lösen können. Wem diese allgemeine (zugegeben sehr abstrakte) Beschreibung nicht ganz geheuer ist, dem sei vielleicht mit dem folgenden Beispiel zum Teile-und-Herrsche-Prinzip geholfen.

Beispiel

Sicherlich kennen Sie ein altes Ratespiel, welches folgendermaßen funktioniert. Person A denkt sich eine Zahl zwischen 0 und 1000. Nun muss Person B durch Fragen erraten, welche Zahl sich A ausgedacht hat und zwar mit möglichst wenig Versuchen. Person A darf aber nur mit Ja oder Nein antworten. Wie kommt B nun relativ schnell an die gesuchte Zahl? Nun, zunächst teilt B den Suchbereich in zwei etwa gleich große Hälften, also 0 bis 500 und 501 bis 1000. Nun fragt B, ob die gesuchte Zahl 500 ist. Falls 500 nicht die gesuchte Zahl ist, fragt B ob die Zahl größer 500 ist. Nehmen wir nun an, A hätte sich die Zahl 250 ausgedacht. A würde nun mit Nein antworten, somit weiß B also schon, dass die gesuchte Zahl zwischen 0 und 500 liegen muss. B teilt also den Suchbereich wieder in zwei Teile und rät weiter. Da die gesuchte Zahl 250 ist, würde B die Zahl schon im nächsten Versuch erraten. Insgesamt würde B für eine solche Suche maximal 10 Rateversuche benötigen. Das Prinzip sollte nun klar sein.

Ablauf

Nun zurück zum binären Suchen. Hier funktioniert es fast genauso wie im Beispiel. Halten wir die einzelnen Schritte noch mal genau fest:
  1. Es wird die Mitte des Suchbereichs ermittelt und geprüft, ob der an dieser Stelle stehende Schlüssel m bereits der gesuchte Schlüssel ist. Wenn dem so ist, ist das Verfahren beendet.
  2. Der aktuelle Suchbereich wird in zwei Teile zerlegt.
  3. Nun muss entschieden werden, in welchem Teilsuchbereich weiter nach dem Schlüssel gefahndet werden soll. Ist der gesuchte Schlüssel kleiner als m, so wird mit dem gleichen Verfahren im linken Teil weitergesucht, ist der Schlüssel größer als m, so wird im rechten Teilsuchbereich mit der Suche fortgefahren.
Rekursiver Algorithmus

Aus obiger Beschreibung ist zu entnehmen, dass man eine solche Suche sehr elegant rekursiv programmieren kann. Im Folgenden sehen Sie einen Java-Quelltext, der eine solche rekursive Suche implementiert:

public class BinaereSuche
{
	
	//Attribute
	int[] feld; 	//speichert das zu durchsuchende Array
	int l;		//linke Grenze des Suchbereichs
	int r;		//rechte Grenze des Suchbereichs
	int m;		//Mitte
	int s;		//das zu suchende Element
	
	//Konstruktor
	public BinaereSuche(int[] feld)
	{
		
		this.feld = feld;
		s = l = r = m = 0;
		
	}
	
	//startet die rekursive Suche
	//führt Initialisierungsarbeiten aus		
	public int sucheRekursiv(int s)
	{
		
		//Array null oder leer?
		if(feld == null || feld.length == 0)
			return -1; //Fehlerwert zurückgeben
		
		//Variablen initialisieren
		l = 0;
		r = feld.length - 1;
		this.s = s;
		
		//startet die eigentliche Rekursion
		return binaerRek();
		
	}
	
	//prüft rekursiv, ob ein bestimmtes Element im
	//Array vorhanden ist und gibt den Index der Position
	//des gefundenen Elements zurück
	public int binaerRek()
	{
		
		m = (l + r) / 2; //Berechnung der Mitte
		print(); //Ausgabe des Status auf der Konsole
		
		//Abbruchbedingung (Rekursionsbasis)
		if(l > r)
			return -1;
		
		//suche s im linken Teilfeld
		if(s < feld[m])
		{
			
			r = m - 1;
			return binaerRek();
			
		}
		//suche s im rechten Teilfeld
		else if(s > feld[m])
		{
			
			l = m + 1;
			return binaerRek();
			
		}
		//s wurde an Position m gefunden
		else
			return m;
				
	}
		
	//gibt den aktuellen Status der Suche auf
	//der Konsole aus
	public void print()
	{
		
		//gibt zuerst den Inhalt des Arrays aus
		for(int i = 0; i < feld.length; i++)
			System.out.print(feld[i] + " ");
		
		System.out.println();
		
		//zeigt die Positionen der einzelnen "Zeiger"
		//innerhalb des Arrays an
		for(int i = 0; i < feld.length; i++)
		{
			
			if(i == m)
				System.out.print("m");
			else if(i == l)
				System.out.print("l");
			else if(i == r)
				System.out.print("r");
			else
				System.out.print(" ");
				
			System.out.print(" ");
				
		}
		
		//zusätzliche Leerzeilen ausgeben				
		System.out.println('\n');
		
	}
	
	//testet die Funktionen der Klasse
	public static void main(String[] args)
	{
	
	int[] a = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 199};
	
	BinaereSuche b = new BinaereSuche(a);
	
	int w = b.sucheRekursiv(5);
	
	System.out.println(w);
	
	}
} 
Sie können den Quelltext per Copy & Paste in ihre Java-Entwicklungsumgebung kopieren und dort ausführen. Der jeweils aktuelle Status des Suchvorgangs wird auf der Konsole ausgegeben, so dass man den Ablauf des Algorithmus leicht nachvollziehen kann.

Diskussion

Ein rekursiver Algorithmus ist natürlich sehr elegant zu implementieren, insbesondere aufgrund der oben angegebenen rekursiven Ablaufbeschreibung. Nachteil ist allerdings, dass bei jedem rekursiven Aufruf Daten auf dem Stack abgelegt werden müssen und so die Speicherkomplexität dieser Implementierung nicht optimal ist. Außerdem kostet jeder Aufruf natürlich Zeit, sodass auch die Laufzeiten länger sind als nötig. Jeder rekursive Algorithmus lässt sich zum Glück auch als iterativer programmieren. Das ist bei diesem Problem auch gar nicht so schwer. Es müssen nur zwei zusätzliche Variable verwaltet werden, die die linke und rechte Grenze des aktuellen Suchbereichs innerhalb des Arrays anzeigen.

Iterativer Algorithmus

Ich habe das Beispielprogramm um den iterativen Algorithmus erweitert. Der komplette Ablauf befindet sich nun innerhalb einer Operation. Es ist nicht mehr nötig eine eigene Operation für die Initialisierung zu schreiben (wie bei der rekursiven Lösung).

public class BinaereSuche
{
	
	//Attribute
	int[] feld; //speichert das zu durchsuchende Array
	int l;		//linke Grenze des Suchbereichs
	int r;		//rechte Grenze des Suchbereichs
	int m;		//Mitte
	int s;		//das zu suchende Element
	
	//Konstruktor
	public BinaereSuche(int[] feld)
	{
		
		this.feld = feld;
		s = l = r = m = 0;
		
	}
	
	//startet die rekursive Suche
	//führt Initialisierungsarbeiten aus		
	public int sucheRekursiv(int s)
	{
		
		//Array null oder leer?
		if(feld == null || feld.length == 0)
			return -1; //Fehlerwert zurückgeben
		
		//Variablen initialisieren
		l = 0;
		r = feld.length - 1;
		this.s = s;
		
		//startet die eigentliche Rekursion
		return binaerRek();
		
	}
	
	//prüft rekursiv, ob ein bestimmtes Element im
	//Array vorhanden ist und gibt den Index der Position
	//des gefundenen Elements zurück
	public int binaerRek()
	{
		
		m = (l + r) / 2; //Berechnung der Mitte
		print(); //Ausgabe des Status auf der Konsole
		
		//Abbruchbedingung (Rekursionsbasis)
		if(l > r)
			return -1;
		
		//suche s im linken Teilfeld
		if(s < feld[m])
		{
			
			r = m - 1;
			return binaerRek();
			
		}
		//suche s im rechten Teilfeld
		else if(s > feld[m])
		{
			
			l = m + 1;
			return binaerRek();
			
		}
		//s wurde an Position m gefunden
		else
			return m;
				
	}
	
	//suche iterativ
	public int sucheIterativ(int s)
	{
		
		//Array null oder leer?
		if(feld == null || feld.length == 0)
			return -1; //Fehlerwert zurückgeben
		
		//Variablen initialisieren
		l = 0;
		r = feld.length - 1;
		this.s = s;
		
		while(l <= r)
		{
			
			m = (r + l) / 2;
			print();
			
			if(s < feld[m])
				r = m - 1;
			else if(s > feld[m])
				l = m + 1;
			else
				return m;
						
		}
		
		return -1;
		
	}
	
	//gibt den aktuellen Status der Suche auf
	//der Konsole aus
	public void print()
	{
		
		//gibt zuerst den Inhalt des Arrays aus
		for(int i = 0; i < feld.length; i++)
			System.out.print(feld[i] + " ");
		
		System.out.println();
		
		//zeigt die Positionen der einzelnen "Zeiger"
		//innerhalb des Arrays an
		for(int i = 0; i < feld.length; i++)
		{
			
			if(i == m)
				System.out.print("m");
			else if(i == l)
				System.out.print("l");
			else if(i == r)
				System.out.print("r");
			else
				System.out.print(" ");
				
			System.out.print(" ");
				
		}
		
		//zusätzliche Leerzeilen ausgeben				
		System.out.println('\n');
		
	}
	
	//testet die Funktionen der Klasse
	public static void main(String[] args)
	{
	
	int[] a = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 199};
	
	BinaereSuche b = new BinaereSuche(a);
	
	int w = b.sucheIterativ(5);
	
	System.out.println(w);
	
	}
}
Analyse

Die Analyse eines Algorithmus beruht im Wesentlichen auf zwei wichtigen Kriterien: Zeit- und Speicherkomplexität. Daraus ergibt sich zunächst die Frage, was Komplexität bedeutet. Salopp gesagt gibt die Komplexität an, wie viel Speicher bzw. wie viel Zeit bei der Verarbeitung von n Elementen verbraucht wird. Diese Definition ist natürlich sehr vage, sollte aber im Moment reichen. Für eine umfassendere Betrachtung schauen Sie bitte unter Quellen nach. Komplexität wird in der so genannten Groß-O-Notation angegeben: O(2n) besagt, dass sich der Zeit- bzw. Speicheraufwand bei größer werdendem n verdoppelt. Es ist vor allem wichtig das Verhalten eines Algorithmus für besonders große n einzuschätzen. Dies wird dann auch asymptotische Zeit- bzw. Speicherkomplexität genannt. Dies ist sozusagen das Grenzverhalten (für Mathematiker: limes) der Funktion f(n) mit O(f(n)). Zum Beispiel steigt der Aufwand bei O(2n²) quadratisch an. Da die 2 vor dem n für sehr sehr große n nicht mehr wichtig ist, wird sie einfach weggelassen: O(n²).

Da wir nun die wichtigsten Begriffe kennen, können wir zunächst eine Analyse der Speicherkomplexität vornehmen. In dem Array sind n Elemente gespeichert, welches jedes für sich eine bestimmte Menge an Speicher benötigt. Also ist die Speicherkomplexität O(n). Bei der Zeitkomplexität wird es allerdings kniffliger: hier muss der Ablauf des Algorithmus etwas genauer unter die Lupe genommen werden: In jedem Schritt wird das Feld in zwei Hälften geteilt. Wie oft kann man ein Feld der Länge n in 2 Hälften zerteilen? Ok, ganz so einfach ist es nicht, nehmen wir also ein Beispiel: wie oft kann man ein Feld der Länge 8 in zwei Hälften zerteilen? Genau! Drei mal. Für n Elemente bedeutet dies ld n, wobei ld der Logarithmus Dualis ist, also der Logarithmus von n zur Basis 2. Die Zeitkomplexität ist also O(ld n).

Die Frage ist nun: wie schnell ist das? Wir haben uns ja gerade schon überlegt, dass für ein Feld der Länge 8 drei Schritte notwendig sind. Denken wir nun in größeren Dimensionen. Was ist mit einer Feldlänge von einer Million Elementen? Nun der Logarithmus von 1.000.000 zur Basis 2 ist 20. Das heißt wir können mit Hilfe der binären Suche in einem Feld von einer Million Elementen ein gesuchtes Element innerhalb von 20 Schritten ausfindig machen.

Quellen

Vorlesung Einführung in die Informatik 2 SS04 (FH Dortmund)
Grundlagen Algorithmen und Datenstrukturen, 3. Auflage, A. Solymosi, U. Grude, Vieweg Verlag


[back to top]



Userdaten
User nicht eingeloggt

Gesamtranking
Werbung
Datenbankstand
Autoren:04503
Artikel:00815
Glossar:04116
News:13565
Userbeiträge:16551
Queueeinträge:06238
News Umfrage
Ihre Anforderungen an ein Online-Zeiterfassungs-Produkt?
Mobile Nutzung möglich (Ipone, Android)
Externe API Schnittstelle/Plugins dritter
Zeiterfassung meiner Mitarbeiter
Exportieren in CSV/XLS
Siehe Kommentar



[Results] | [Archiv] Votes: 1137
Comments: 0