binäre suche mit c

[Gast]

Hi ich hab versucht, die Binäre Suche innerhalb eines Arrays in C zu schreiben.
Anbei mein Code und die Bitte um Überprüfung.
Durchgespielt auf dem Papier komm ich zu den gleichen Werten und Durchlaufzahlen wie das Programm


#include <iostream>

using namespace std;
int binSearch(int,int,int);
int array[]={1,2,3,4,5,6,7,8,9,10};
int count=0;

int main(void)
{
int erg=binSearch(0,9,6);
cout<<"\nLäufe gesamt: "<<count<<"\n";
cout<<"Ergebnis: "<<erg;
}

int binSearch(int start,int ende,int suche)
{
int mitte=(start+ende)/2;
cout<<count+1<<". Lauf."<<" Verwendete Mitte:"<<array[mitte]<<"\n";
count++;
while(1)
{
if(array[mitte]==suche)
{
return array[mitte];
}
else if(array[mitte]<suche)
{
start=mitte+1;
return(binSearch(start,ende,suche));
}
else if(array[mitte]>suche)
{
ende=mitte-1;
return(binSearch(start,ende,suche));
}
}
}


Ausgabe:

1. Lauf. Verwendete Mitte:5
2. Lauf. Verwendete Mitte:8
3. Lauf. Verwendete Mitte:6

Läufe gesamt: 3
Ergebnis: 6

[robobimbo]

sieht mir ganz ok aus, ganz normale implementierung einer binären suche halt.
mach mal einen extremtest und lasse es auf ein array der größe 1 los (also nur 1 element) - damit lässt sichimmer gut testen wie robust so ein zeug ist.

aber wozu brauchst du das while(1) in der funktion?

[Trap]

int mitte=(start+ende)/2;

Das funktioniert nicht für alle möglichen Werte von start und ende.

[Gast]

garnicht :) hab das while(1) entfernt und ging trotzdem.
nur dein Fehler machte meinem prog noch problemen d.h. Länge von array=1 und suche=1 = endlosschleife. auch mit länge =2 und suchzahl=2 -> schleife.
hab das jetzt unschön mit einer abfrage abgefangen, wobei ich die ursache noch nicht erkenne.

hier die neueste version mit komfortabler eingabe :)



#include <iostream>

using namespace std;
int binSearch(int*,int,int,int);
void fillArray(int*,int);
int count=0;

int main(void)
{
unsigned int len;
int suche;
cout<<"Binbäre Suche innerhalb eines Arrays\n";
cout<<"Grösse des Arrays angeben [maximale Länge = unsigned int]\n";
cin>>len;
cout<<"Zu suchende Zahl eingeben: \n";
cin>>suche;
if(suche>len||suche==len)
{
cout<<"Fehler!";
return 0;
}
int array[len];
int* ptr;
ptr=&array[0];
fillArray(ptr,len);
int erg=binSearch(ptr,0,len,suche);
cout<<"Ergebnis: "<<erg;
return 0;
}

void fillArray(int* t,int ende)
{
for(int i=0;i<ende;i++)
{
t[i]=i;
}
}

int binSearch(int* array,int start,int ende,int suche)
{
int mitte=(start+ende)/2;
cout<<count+1<<". Lauf."<<" Verwendete Mitte:"<<array[mitte]<<"\n";
count++;
if(array[mitte]==suche)
{
return array[mitte];
}
else if(array[mitte]<suche)
{
start=mitte+1;
return(binSearch(array,start,ende,suche));
}
else if(array[mitte]>suche)
{
ende=mitte-1;
return(binSearch(array,start,ende,suche));
}
}

[Senior Sanchez]

int mitte=(start+ende)/2;

Das funktioniert nicht für alle möglichen Werte von start und ende.

Richtig.

Der uralte Fehler, der Jahrzehnte in den Implementierungen steckte und zum Beispiel glaube erst bei Java 5 korrigiert wurde.