Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Binäre Suche funktioniert nicht immer?!


Slice - So 01.11.09 16:12
Titel: Binäre Suche funktioniert nicht immer?!
habe folgendes Problem: ich habe ein Array, in dem ich mit der binären Suche nach einer zahl suchen möchte. Manche Zahlen werden gefunden und manche nicht (obwohl sie im array stehen) und das programm hängt sich auf....
hier mal der Quelltext:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
 
public
    { Public-Deklarationen }
    procedure suchen(l,r,x: integer);     //l= anfang array und r= ende arry x = gesuchte zahl
  end;

var
  Form1: TForm1;
  liste: array[1..10of integer;
  k: integer;

implementation

{$R *.DFM}


procedure TForm1.Button1Click(Sender: TObject);  //Zahlen ins Array speichern
begin
Listbox1.Clear;
for k := 1 to 10 do
begin
z:= z+1;
liste[k]:= z;
Listbox1.Items.Add(IntToStr(liste[k]));       //in Listbox ausgeben
end;
end;

procedure TForm1.suchen;                //die procedure zum suchen
var
m: integer;
gefunden: boolean;
begin
gefunden:= false;
while (gefunden=false) and (l<=r) do
 begin
 m:= (l+r) div 2;  //die Mitte des Arrays
 if x = liste[m] then gefunden:= true
  else
  if x < liste[m]  then r:= m+1
   else
   l:= x-1;
   end;

if gefunden = true then ShowMessage(' Die Zahl wurde gefunden!')
else Showmessage('nicht gefunden');
end;



procedure TForm1.Button2Click(Sender: TObject);
begin
suchen(1,10, StrToInt(Edit2.Text));       //procedure aufrufen
end;

end.


ich brauch so schnell wie möglich hilfe, brauch das für ne Arbeit (am dienstag)...^^


elundril - So 01.11.09 16:24

du weißt das eine binäre suche eigentlich nur bei sortierten listen funktioniert? da du in dein array die zahlen irgendwie einfügst kannst du ja ned sicher sein das die sortiert sind, oder?

lg elundril


Slice - So 01.11.09 16:36

user profile iconelundril hat folgendes geschrieben Zum zitierten Posting springen:
du weißt das eine binäre suche eigentlich nur bei sortierten listen funktioniert? da du in dein array die zahlen irgendwie einfügst kannst du ja ned sicher sein das die sortiert sind, oder?

lg elundril


habs mal sortier (siehe 1. post, ist einfach von 1-10)

die zahlen 2-8 werden auch gefunden, aber bei 1,9 und 10 hängt es sich auf (und auch bei zahlen die nicht im array stehen)...


elundril - So 01.11.09 16:59

warum schreibst du im elsezweig l := x-1? solltest du nicht m+1 schreiben? und im thenzweig r := m -1.

lg elundril


Slice - So 01.11.09 17:02

user profile iconelundril hat folgendes geschrieben Zum zitierten Posting springen:
warum schreibst du im elsezweig l := x-1? solltest du nicht m+1 schreiben? und im thenzweig r := m -1.

lg elundril


omg es funzt :D dankeschön^^ ich bin einfach zu blind für solche kleinen fehler^^ natürlich muss es so sein, wie du geschrieben hast....