Nächste Seite: A.2.5 Einfach verkettete Liste Aufwärts: A.2 Lösungen Vorherige Seite: A.2.3 Summenbildung Inhalt
Der Fehler im angegebenen Algorithmus besteht darin, daß nach dem
Prüfen von a[mid] gegen das gesuchte das Feld auf eines der
Teilfelder inklusive dem bereits geprüften Element an der Stelle mid
geteilt wird (also entweder auf 0 .. mid oder mid .. max).
Das bereits geprüfte Element darf aber nicht im Feld verbleiben
(man müßte also reduzieren auf 0 .. mid-1 oder mid+1 .. max):
erstens ist es uneffektiv, das Feld nicht so schnell wie möglich zu
reduzieren, zweitens kann es je nach Eingangsdaten zu einer
Endlosschleife kommen (nämlich in dem Fall, daß ein gesuchtes Element
nicht im Feld enthalten ist, aber aufgrund der Sortierung zwischen den
ersten beiden Elementen des aktuellen Teilfeldes liegen
müßte). Dann wird von einem Schritt zum nächsten das Feld nicht mehr reduziert.A.1
Hier die Musterlösung in Java (in Form einer einzigen Klasse; der Übersichtlichkeit zuliebe alles in einer Klasse und nur für ganze Zahlen):
// Time-stamp: "03.05.03 18:20 binsuch.java klaus@wachtler.de"
//
// Testprogramm zur Binären Suche.
// javac binsuch.java && java binsuch
import java.util.*;
import java.io.*;
public class binsuch
{
// die eigentliche Suche muß sowohl mit dem ursprünglichen gesamten
// Feld, als auch mit Teilfeldern durchgeführt werden können.
// Damit die Teilfelder nicht durch aufwendiges Kopieren erzeugt
// werden müssen, kann man einfach immer das gesamte Feld an den
// nächsten Rekursionsschritt übergeben, und als zusätzliche
// Parameter den Anfangs- und den Endindex des zu verwendenden
// Teilfeldes.
// Um den ersten Aufruf einfacher und fehlerfrei zu ermöglichen,
// wird die Methode binsuch() mit zwei Versionen überlagert:
// Die erste Version wird nur mit dem Feld un dem zu suchenden
// Wert aufgerufen, die zweite mit den Grenzen für ein Teilfeld.
private static Integer binsuch( Integer Gesamtfeld[],
int zusuchen
)
{
// einfach die Parameter auf die eigentliche Suche umsetzen:
return binsuch( Gesamtfeld, 0, Gesamtfeld.length-1, zusuchen );
}
private static Integer binsuch( Integer Teilfeld[], int von, int bis,
int zusuchen
)
{
if( bis<von )
{
// leeres Feld? Nichts gefunden!
return null;
}
else if( bis==von )
{
// nur ein Element; vergleichen und ggf. zurückgeben:
return ( (Teilfeld[bis]).intValue()==zusuchen ? Teilfeld[bis] : null );
}
else
{
// Mehr als ein Element
// Mitte suchen, und ggf. links oder rechts suchen:
int index_Mitte = ( von + bis )/2;
if( Teilfeld[index_Mitte].intValue()==zusuchen )
{
// Zufällig getroffen!
return Teilfeld[index_Mitte];
}
else if( Teilfeld[index_Mitte].intValue()>zusuchen )
{
// Mitte ist zu groß, also links weitersuchen
return binsuch( Teilfeld, von, index_Mitte-1, zusuchen );
}
else
{
// Mitte zu klein, also in rechter Hälfte suchen:
return binsuch( Teilfeld, index_Mitte+1, bis, zusuchen );
}
}
}
private static void einfacherTest()
{
// Um Objekte zu haben, nehmen wir nicht int, sondern
// Integer. Dann kann man als Ergebnis der Suche den Wert null
// liefern, wenn die Suche erfolglos ist.
Integer a1[] = new Integer[7];
a1[0] = new Integer(12);
a1[1] = new Integer(45);
a1[2] = new Integer(60);
a1[3] = new Integer(70);
a1[4] = new Integer(80);
a1[5] = new Integer(100);
a1[6] = new Integer(110);
Integer gefunden = binsuch( a1, 105 );
if( gefunden!=null )
{
System.out.println( "In a1[] gefunden: " + gefunden );
}
else
{
System.out.println( "Wert in a1[] nicht gefunden" );
}
}
private static void TestMitEinlesen()
{
// Feld für die gelesenen und zu durchsuchenden Werte:
Integer a2[] = null;
try
{
// zu lesende Datei ist ein BufferedReader:
BufferedReader in
= new BufferedReader( new FileReader( "werte.dat" ) );
String zeile; // hier kommt je eine gelesene Zeile hin
while( (zeile=in.readLine())!=null ) // Schleife über
// alle Zeile der Datei
{
try
{
// versuchen, die Zeile in eine int zu verwandeln
// und speichern (dazu das Feld verlängern):
Integer neuesFeld[] = new Integer[a2==null ? 1 : a2.length+1];
for( int i=0; i<neuesFeld.length-1; i++ )
{
neuesFeld[i] = a2[i];
}
neuesFeld[neuesFeld.length-1] = new Integer( Integer.parseInt( zeile ) );
a2 = neuesFeld;
}
catch( Exception e )
{
System.out.println( "Konvertieren zu int geht nicht" );
}
}
in.close(); // Datei wieder schließen
}
catch( Exception e )
{
}
Integer gefunden = binsuch( a2, 24 );
if( gefunden!=null )
{
System.out.println( "In a2[] gefunden: " + gefunden );
}
else
{
System.out.println( "Wert in a2[] nicht gefunden" );
}
}
public static void main( String args[] )
{
einfacherTest();
TestMitEinlesen();
}
} // public class binsuch
Hier die Musterlösung in C++:
// Time-stamp: "03.05.03 17:39 binsuch.cpp klaus@wachtler.de"
//
// Musterloesung in C++ zu folgender Aufgabenstellung:
// Das Suchverfahren "`Binäres Suchen"' arbeitet nach folgendem Algorithmus:
//
// Algorithmus: Binäre Suche im Array a[min .....max] (min = 0, max = n)
// (1) wähle ein mittleres Element des Arrays a[mid]
// (2) if (a[mid].key == gesuchterKey)
// Suche erfolgreich
// else
// if (a[mid].key < gesuchterKey)
// betrachte die linke Hälfte des Arrays, also 0 .. mid
// else
// betrachte die rechte Hälfte des Arrays, also mid.. max
// (3) if (betrachtetes Array == leer)
// Suche erfolglos
// else
// beginne bei Schritt 1
//
// Implementieren Sie den Algorithmus so, daß in einem sortierten Feld
// von Integer-Zahlen gesucht werden kann. Geben Sie jedesmal, wenn Sie
// ein Teilfeld durchsuchen, die Indizes der Grenzen und des mittleren
// Elements aus. Geben Sie am Ende den Index des gefundenen Elements
// bzw. eine Meldung für die erfolglose Suche aus.
//
// Testen Sie Ihren Algorithmus zunächst mit einfachen Feldern, die Sie
// direkt im Programmcode initialisieren.
//
// Erweitern Sie ihr Programm so, daß die zu durchsuchende Zahlenfolge
// aus einer Datei eingelesen werden kann. Hierzu sollen Sie folgende
// Ein-/Ausgabe realisieren:
//
// - Lesen Sie den Namen der Datei, in der die zu durchsuchende
// Zahlenfolge steht von der Tastatur ein.
// - Lesen Sie die Zahlenfolge aus der Datei ein.
// - Das Programm soll selbständig herausfinden, wieviele
// Elemente die Zahlenfolge enthält und das Feld entsprechend
// dimensionieren.
// - Gehen Sie davon aus, daß die Elemente in der
// einzulesenden Datei jeweils durch Leerzeichen getrennt sind.
// - Lesen Sie die zu suchende Zahl von der Tastatur ein.
// - Fangen Sie Fehler beim Einlesen ab und überprüfen Sie,
// ob die eingelesene Zahlenfolge sortiert ist.
//
// Geben Sie zum Schluß den Algorithmus richtig an (im Gegensatz zum oben
// gegebenen).
//
// ANSI-C++
//
// Linux: g++ -Wall binsuch.cpp && a.out
//
// VC++ 6.0: cl /Zi /GX auklid.cpp
// .\binsuch
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int *binsuch( int feld[], size_t l, int zusuchen )
{
if( l<1 )
{
// leeres Feld? Nichts gefunden!
return NULL;
}
else if( l==1 )
{
// nur ein Element; vergleichen und ggf. zurückgeben:
return ( feld[0]==zusuchen ? &feld[0] : NULL );
}
else
{
// Mehr als ein Element
// Mitte suchen, und ggf. links oder rechts suchen:
int index_Mitte = l/2;
if( feld[index_Mitte]==zusuchen )
{
// Zufällig getroffen!
return &feld[index_Mitte];
}
else if( feld[index_Mitte]>zusuchen )
{
// Mitte ist zu groß, also links weitersuchen
return binsuch( feld, index_Mitte, zusuchen );
}
else
{
// Mitte zu klein, also in rechter Hälfte suchen:
return binsuch( &feld[index_Mitte+1], l - index_Mitte - 1, zusuchen );
}
}
} // int *binsuch( int feld[], size_t l, int zusuchen )
void einfacherTest()
{
// einfaches, sortiertes Feld zum Testen:
int a1[] = { 12, 45, 60, 70, 80, 100, 110 };
const size_t a1l = sizeof(a1)/sizeof(a1[0]); // Feldlänge
int *p_gefunden = binsuch( a1, a1l, 46 );
if( p_gefunden )
{
cout << "In a1[] gefunden: " << *p_gefunden << endl;
}
else
{
cout << "Wert in a1[] nicht gefunden." << endl;
}
} // void einfacherTest()
void TestMitEinlesen()
{
// Datei mit den sortierten Werten:
string Dateiname;
cout << "Bitte den Namen einer Datei mit sortierten int-Werten:" << endl;
cin >> Dateiname;
int *arr = NULL;
size_t larr = 0;
{ // Einlesen
ifstream f( Dateiname.c_str() );
int wert;
while( ( f>>wert ) )
{
// Feld um ein Element verlängern:
arr = (int*)realloc( arr, ++larr*sizeof(int) );
if( !arr )
{
cerr << "kein Speicher!\n";
exit( 1 );
}
arr[larr-1] = wert;
}
} // Einlesen
{ // Testen, ob sortiert
for( size_t i=1; i<larr; i++ )
{
if( !( arr[i-1]<arr[i] ) )
{
cerr << "Feld nicht sortiert!\n";
exit( 1 );
}
}
} // Testen, ob sortiert
// Welcher Wert soll gesucht werden?
cout << "Gesuchten Wert eingeben:" << endl;
int gesucht;
cin >> gesucht;
int *p_gefunden = binsuch( arr, larr, gesucht );
if( p_gefunden )
{
cout << "In " << Dateiname << " gefunden: " << *p_gefunden << endl;
}
else
{
cout << "Wert in " << Dateiname << " nicht gefunden." << endl;
}
// allokierten Speicher wieder freigeben:
free( arr ); arr = NULL; larr = 0;
} // void TestMitEinlesen()
int main( int nargs, char **args )
{
einfacherTest();
TestMitEinlesen();
return 0;
} // main( int nargs, char **args )
In der Standardbibliothek von C ist bereits eine Funktion bsearch() enthalten, die in Feldern beliebigen Typs suchen kann. Dazu ist beim Aufruf eine Funktion (beziehungsweise ihre Adresse) anzugeben, die anhand von zwei Zeigern auf Feldelemente zurückliefert, welcher der beiden Werte kleiner ist (siehe man 3 bsearch unter Unix/Linux oder [KW-C]).
Eine mögliche Implementation mit zugehörigem Testprogramm sieht so aus:
// Time-stamp: "24.05.02 11:30 bsearch.cpp Administrator@AW41"
//
// ANSI-C
//
// Linux: g++ -Wall bsearch.cpp && a.out
// VC++ 6.0: cl
#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
// sucht in einem sortierten Feld (*base)[] nach einem
// Element, für das die Funktion (*compar)() Gleichheit mit dem
// Schlüssel (*key) verspricht, und liefert einen Zeiger auf
// das gefundene Element, oder NULL
// (entspricht dem Original-bsearch() nach ANSI-C)
void *bsearch( const void *key,
const void *base,
size_t nmemb,
size_t size,
int (*compar)( const void *, const void * )
)
{
switch( nmemb )
{
case 0: // leeres Feld
return NULL;
case 1: // ein Element: vielleicht ein Treffer
return ( (*compar)( base, key )==0 ? (void *)base : NULL );
default : // mehr als zwei Elemente
// Teilen, und suchen lassen:
{
// Etwa die Mitte des Feldes:
size_t n1 = nmemb/2;
// Zeiger auf mittleres Element:
const void *p1 = (const char*)base+(n1*size);
// Dieses mittlere Element mit Schlüssel vergleichen:
int v1 = (*compar)( p1, key );
if( v1==0 )
{
// Schlüssel genau getroffen
return(void *) p1;
}
else if( v1<0 )
{
// base[n1] kleiner als Schlüssel;
// also in der oberen Hälfte suchen.
// base[n1] braucht schon nicht mehr betrachtet
// zu werden.
return bsearch( key,
(const char*)p1+size,
nmemb - n1 - 1,
size,
compar
);
}
else
{
// base[n1] größer als Schlüssel;
// also in der unteren Hälfte suchen.
// base[n1] braucht schon nicht mehr betrachtet
// zu werden.
return bsearch( key,
base,
n1,
size,
compar
);
}
}
} // switch
} // bsearch()
// Testdatentyp für Feldelemente:
typedef struct
{
double d;
char s[100];
} s_t;
// Vergleichsfunktion für obigen Datentyp s_t:
int vergl_f( const void *p1, const void *p2 )
{
if( ((const s_t*)p1)->d > ((const s_t*)p2)->d )
{
return 1;
}
else if( ((const s_t*)p1)->d < ((const s_t*)p2)->d )
{
return -1;
}
else
{
return 0;
}
}
// zu durchsuchendes Feld:
s_t f[] =
{
{ 3.141592654, "pi" },
{ 2.718281828, "e" },
{ 53.00000000, "w" },
{ 1.000000000, "eins" },
{ 2.000000000, "zwoo" },
{ 13.00000000, "drölf" },
};
// Anzahl Feldelemente:
const int l = sizeof(f)/sizeof(f[0]);
// Testprogramm:
int main( int nargs, char **args )
{
qsort( f,
l,
sizeof(f[0]),
vergl_f
);
// Schleife, bis der Benutzer -1 eingibt:
while( 1 )
{
double wert;
printf( "Bitte einen Wert (Ende mit -1): " );
if( scanf( "%lf", &wert )!=1 || wert==-1.0 )
{
break;
}
s_t key = { wert, "" };
s_t *p = (s_t *)bsearch( &key,
f,
l,
sizeof(f[0]),
vergl_f
);
if( p )
{
printf( "Gefunden: %f %s\n", p->d, p->s );
}
else
{
printf( "nichts gefunden!\n" );
}
} return 0; } /* main( int nargs, char **args ) */