visitor (0 QPoints)
  • FR
  • EN
  • NL
  • DE
  • ES
315 experts, 1193 registered users, 1659 questions already answered
European Experts Exchange, the very best site for high-quality IT solutions

New Improved Search!

 


05/10/2011 1h30 : Steve Jobs is dead, the father of Apple ][ is gone, we are all orphaned.

Languages :: Pascal :: Help with Binary search
By: sajidaziz U.S.A.  Date: 20/05/2003 00:00:00  English  Points: 300 Status: Answered
Quality : Excellent
I am trying to get this program to randomise, and then to count search until sorted, then to find the number of times it appears.

Program Uncover;
Uses Crt;

VAR Low, Middle, High, Target, Count, ErrCode : Integer;
N: Array[1..1000] Of Integer;
Line : Byte;
TStr : String;
Any_Key :Char;

Begin
Clrscr;

For Count := 1 To 100 Do
begin
N[Count] := count;
write(n[count]:5);
end;
delay(3000);
Clrscr;
Writeln('An array of integers 1-100 has been created.');
Writeln('Let''s use Binary Search to target a chosen value.');
Writeln;
Low := 1;
High := 100;

Repeat
Gotoxy (39,5);
Write(' ');
Gotoxy(9,5);
Write('Enter an Integer 1 - 100 : ');
Readln(Tstr);
Val(Tstr, Target, ErrCode);
Until ((Target > 0) And (Target <= 100) And (ErrCode = 0));
Gotoxy(39,5);
Writeln(Target, ' ');
Writeln;
Writeln('Low' :5, 'High' :10,'Middle' :10,'Content' :10);
Writeln('__________________________________________');
Repeat
Middle := (High+Low) Div 2;
Writeln(Low:5,High:10,Middle:10,N[Middle]:10);
If N[Middle] > Target Then
High := Middle -1
Else
Low := Middle + 1;
Until (N[Middle] = Target);
Line := WhereY - 1;
Gotoxy(40,Line);

Writeln('<-- Target found at current ''Middle''.');
Writeln('---------------------------------------');
Gotoxy(28,24);
Write('Press any Key to Continue ');
Any_Key := Readkey
End.

PLZ HELP!!!!
By: VGR Date: 20/05/2003 19:32:00 English  Type : Comment
that's the dichotomic search.

and what is the problem please ? :D

'cause the program seems ok and produces good results :

Enter an Integer 1 - 100 : 25
25

Low High Middle Content
__________________________________________
1 100 50 50
1 49 25 25
<-- Target found at current 'Middle'.
---------------------------------------
By: VGR Date: 20/05/2003 19:34:00 English  Type : Comment
ok, your problem is that "you want to randomize" (in stead of sequential numbers 1..100) and "sort" them, then after finding the "pivot" you would like "the count of occurences"

is that it ?
By: sajidaziz Date: 20/05/2003 20:16:00 English  Type : Comment
That is correct VGR, thats exactly what I want it to do, I'm just going through my tutorial and i've managed or i think i have to randomize the numbers.
By: Okey Date: 20/05/2003 20:30:00 English  Type : Comment
Put initialy Randomize to your proggy!
This lead to that the Time will be Put on the Randseed-Longint,
so its starting value is randomised!
Later You simply use Random (RValue) where RValue is your greatest Random value instead of reading them with read(ln) from Keyboard or File device.


Begin
...
RANDOMIZE;
...

{instead Readln(Value) do this :}

Value :=Random(1000);

...
End.

You know ???
By: VGR Date: 20/05/2003 20:34:00 English  Type : Answer
I'm not sure you'll like it, because the dichotomic search is no longer necessary 8-))

But I may introduce again (by losing time and doing unnecessary work) if you prefer 8-)

Program testdicho;

(* for my Delphi {$APPTYPE CONSOLE} *)

Use Crt;

VAR Low, Middle, High, Target, Count, ErrCode : Integer;
N, Z : Array[1..1000] Of Integer;
Line : Byte;
TStr : String;
Any_Key :Char;
j : Integer; (* Byte more appropriate, but let's stay as simple as possible *)

Begin
Clrscr;

(* previously : sequential numbers
For Count := 1 To 100 Do
begin
N[Count] := count;
write(n[count]:5);
end;
*)
(* now randomize *)
Randomize;
For Count := 1 To 100 Do
begin
Z[Count] := Trunc(Random(100)+1); (* between 1 and 100 *)
write(Z[count]:5);
end;

(* now "sort" the numbers *)
(* tri instantané Vasiljevic 1982 dans THEORIC *)
WriteLn;
WriteLn('Sorting...');
For Count := 1 To 100 Do N[Count]:=0;
For Count := 1 To 100 Do Inc(N[Z[Count]]);
(* N is now sorted, let's display it *)
WriteLn('sorted array : ');
(* Z[] is the array of occurences, 99% of the work is already done ;-) *)
For Count := 1 To 100 Do If N[Count]>0 Then For j:=1 to N[Count] Do Write(Count:5);
WriteLn;

Repeat
Gotoxy (39,5);
Write(' ');
Gotoxy(9,5);
Write('Enter an Integer 1 - 100 : ');
Readln(Tstr);
Val(Tstr, Target, ErrCode);
Until ((Target > 0) And (Target <= 100) And (ErrCode = 0));
Gotoxy(39,5);
Writeln(Target, ' ');
Writeln;
If N[Target]>0 (* number present, else absent *)
Then Begin
Writeln(Low:5,High:10,Middle:10,N[Middle]:10);
Writeln('<-- Target found, present ',N[Target],' times.');
Writeln('---------------------------------------');
End
Else Begin
WriteLn(target,' is not present in the dataset.');
Writeln('---------------------------------------');
End; (* if number represented, then, else *)
Line := WhereY - 1;
Gotoxy(40,Line);

Gotoxy(28,24);
Write('Press any Key to Continue ');
Any_Key := Readkey (*readln; is more compatible/portable*)
End.
By: VGR Date: 20/05/2003 21:41:00 English  Type : Comment
OK, here's a TRUE dichotomic program fulfilling your requirements.

----------- results
sorted rebuilt "normal" array :
1 2 3 3 5 6 7 9 11 11 13 14 15 16 18 18
19 19 20 21 23 24 24 25 26 27 28 29 32 33 33 35
36 37 39 41 41 42 44 46 47 48 48 50 52 53 53 53
54 54 56 56 57 58 60 60 61 65 66 69 71 71 71 72
72 73 73 75 75 76 77 78 78 78 79 81 82 83 88 89
92 92 94 94 95 95 96 97 98 98 98 98 98 98 99 99
99 99 99 100
An array of integers 1-100 has been created.
Let's use Binary Search to target a chosen value.

Enter an Integer 1 - 100 : 50
50

Low High Middle Content
__________________________________________
1 100 50 54
1 49 25 26
26 49 37 41
38 49 43 48
44 49 46 53
44 45 44 50
<-- Target found at current 'Middle'.
---------------------------------------
Press any Key to Continue


sorted rebuilt "normal" array :
1 1 2 3 3 4 4 7 8 9 11 11 11 12 13 14
19 19 19 21 21 22 22 24 25 25 26 29 29 30 31 31
31 31 33 33 36 37 38 39 40 40 40 43 44 44 44 45
47 48 49 51 51 52 53 53 54 57 58 58 59 64 65 65
66 66 67 68 68 68 69 72 74 74 74 76 76 77 80 80
81 82 84 84 84 85 87 88 90 90 91 93 94 94 95 96
98 98 99 100
An array of integers 1-100 has been created.
Let's use Binary Search to target a chosen value.

Enter an Integer 1 - 100 : 5
5

Low High Middle Content
__________________________________________
1 100 50 48
1 49 25 25
1 24 12 11
1 11 6 4
7 11 9 8
7 8 7 4
Value 5 not present in array.

----------- source
Program testdicho;

{$UNDEF DELPHIHERE}

{$IFDEF DELPHIHERE}
{$APPTYPE CONSOLE}
{$ENDIF}

{$IFNDEF DELPHIHERE}
Use Crt;
{$ENDIF}

VAR Low, Middle, High, Target, Count, ErrCode : Integer;
N, Z : Array[1..1000] Of Integer;
Line : Byte;
TStr : String;
Any_Key : Char;
i, j : Integer; (* Byte more appropriate, but let's stay as simple as possible *)

Begin
{$IFNDEF DELPHIHERE}Clrscr;{$ENDIF}

(* previously : sequential numbers
For Count := 1 To 100 Do
begin
N[Count] := count;
write(n[count]:5);
end;
*)
(* now randomize *)
Randomize;
For Count := 1 To 100 Do
begin
N[Count] := Trunc(Random(100)+1); (* between 1 and 100 *)
write(N[count]:5);
end;

(* now "sort" the numbers *)
(* tri instantané Vasiljevic 1982 dans THEORIC *)
WriteLn;
WriteLn('Sorting...');
For Count := 1 To 100 Do Z[Count]:=0;
For Count := 1 To 100 Do Inc(Z[N[Count]]);
(* N is now sorted, let's display it *)
WriteLn('sorted array : ');
(* Z[] is the array of occurences, 99% of the work is already done ;-) *)
For Count := 1 To 100 Do If Z[Count]>0 Then For j:=1 to Z[Count] Do Write(Count:5);
WriteLn;
(* rebuild sorted array *)
i:=0;
For Count := 1 To 100 Do
If Z[Count]>0 Then For j:=1 to Z[Count] Do Begin Inc(i); N:=Count; End;
(* rebuild array to apply normal dichotomic algorithm on it *)
(* N is now sorted, let's display it *)
WriteLn('sorted rebuilt "normal" array : ');
For Count := 1 To 100 Do Write(N[Count]:5);
WriteLn;

(* resume normal dichotomic search *)
{$IFNDEF DELPHIHERE}Clrscr;{$ENDIF}
Writeln('An array of integers 1-100 has been created.');
Writeln('Let''s use Binary Search to target a chosen value.');
Writeln;
Low := 1;
High := 100;

Repeat
{$IFNDEF DELPHIHERE}Gotoxy (39,5);{$ENDIF}
Write(' ');
{$IFNDEF DELPHIHERE}Gotoxy(9,5);{$ENDIF}
Write('Enter an Integer 1 - 100 : ');
Readln(Tstr);
Val(Tstr, Target, ErrCode);
Until ((Target > 0) And (Target <= 100) And (ErrCode = 0));
{$IFNDEF DELPHIHERE}Gotoxy(39,5);{$ENDIF}
Writeln(Target, ' ');
Writeln;
Writeln('Low' :5, 'High' :10,'Middle' :10,'Content' :10);
Writeln('__________________________________________');
Repeat
Middle := (High+Low) Div 2;
Writeln(Low:5,High:10,Middle:10,N[Middle]:10);
If N[Middle] > Target Then
High := Middle -1
Else
Low := Middle + 1;
Until (N[Middle] = Target)or(High=Low);
{$IFNDEF DELPHIHERE}
Line := WhereY - 1;
Gotoxy(40,Line);
{$ENDIF}

If N[Middle]=Target Then
Begin
Writeln('<-- Target found at current ''Middle''.');
Writeln('---------------------------------------');
End Else WriteLn('Value ',Target,' not present in array.');
(* here, to display the number of occurences, we've two choice :
-the "intelligent" way : Z[Count] is the number of occurences ;-)
-the "normal" way : goind linearly down and up from Middle in search for a different value in N[]
*)
{$IFNDEF DELPHIHERE}Gotoxy(28,24);{$ENDIF}
Write('Press any Key to Continue ');
{$IFNDEF DELPHIHERE}
Any_Key := Readkey;
{$ELSE}
ReadLn;
{$ENDIF}
End.
By: VGR Date: 22/05/2003 20:58:00 English  Type : Comment
ping
By: VGR Date: 23/05/2003 17:34:00 English  Type : Comment
allo ?
By: VGR Date: 28/05/2003 08:40:00 English  Type : Comment
your problem was solved neat and clean, so please choose an Answer and close the Question.
By: Okey Date: 28/05/2003 13:52:00 English  Type : Comment
VGR is right !(
Else explain your question next time better!
More details about what you want to do and
not only what you did,
because it leads to suggestions about your aim!
By: VGR Date: 30/05/2003 08:08:00 English  Type : Comment
ping

forced answer ?
By: Okey Date: 30/05/2003 08:12:00 English  Type : Comment
Maybe too heavie stuff ????
By: sajidaziz Date: 01/06/2003 07:03:00 English  Type : Comment
Sorry not been able to reply or close the question,
Your suggestions helped and i've managed to write the program.
Try it.


Program Uncover;
Uses Crt;

VAR Count,pass,check,hold,low,middle,high,target,nu,nl,total,errcode : Integer;
N: Array[1..384] Of Integer;
line:byte;
Tstr : string;
Any_Key : char;

Begin
Clrscr;
randomize;
For Count := 1 To 384 Do
begin
N[count] := random(100) + 1;
write(N[count]:5);
end;

delay(5000);

for pass := 1 to 384 do
for check := 1 to 383 do
begin
if n[check] > n[check+1] then
begin
hold := n[check];
n[check] := n[check+1];
n[check+1] := hold;
end;
end;

For Count := 1 To 384 Do
begin
write(N[count]:5);
end;

delay(5000);
high:=384;
low:=1;
clrscr;

Repeat
Gotoxy (39,5);
Write(' ');
Gotoxy(9,5);
writeln('A random list of 100 numbers between 1-100 has been created');
writeln('Enter a number to see how many times it occurs');
Write('Enter an Integer 1 - 100 : ');
Readln(Tstr);
clrscr;
Val(Tstr, Target, ErrCode);
Until ((Target > 0) And (Target <= 100) And (ErrCode = 0));
Gotoxy(39,5);
Writeln(Target, ' ');
Writeln;
Writeln('Low' :5, 'High' :10,'Middle' :10,'Content' :10);
Writeln('__________________________________________');
Repeat
Middle := (High+Low) Div 2;

If N[Middle] > Target Then
High := Middle -1
Else
Low := Middle + 1;
Until (N[Middle] = Target);
clrscr;
nu:=0;
while n[middle]=target do
begin
writeln('Target',target,' found at position ',middle);
nu:=nu+1;
middle:=middle+1;
end;
middle:=middle-nu-1;
nl:=0;
while n[middle]=target do
begin
writeln('Target ',target,' found at position ',middle);
nl:=nl+1;
middle:=middle-1;
end;
total:=nl+nu;
Writeln('The number occurs ',total,' times');
readln;
end.


Thanx you to everyone that helped!!!!!!!!!!
By: Okey Date: 10/06/2003 17:01:00 English  Type : Comment
Close the question or reply to given answers,
else you'll get ping-spamed!

Your program runs! ... tada ...

Ping

Ping

Ping
By: Okey Date: 10/06/2003 17:03:00 English  Type : Comment
If you got an ordinal Value Array then Bits minus last Non-Zero Bit will give you the count of search tries!

Ping

Ping ping

Ping
By: Okey Date: 11/06/2003 04:43:00 English  Type : Comment
Ping

No reply

Ping ping

Ping

Why are you offering 250 Points and don't reply?

Ping

Ping ping!
By: ziolko Date: 16/06/2003 23:58:00 English  Type : Comment
another homework done no points given Q, thats why I'm not posting any comments on such Qs.
ziolko.
By: VGR Date: 17/06/2003 00:06:00 English  Type : Comment
I begin thinkng like you
By: sajidaziz Date: 23/06/2003 07:53:00 English  Type : Comment
Frankly none of the answers you gave were correctly answering my question, however if you want me to close the3 question and accept an answer, It is going to be VGR for trying to help me.

Thanx you all

Do register to be able to answer

©2010 These pages are served without commercial sponsorship. (No popup ads, etc...). Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE.
Please DO link to this page! Post to Twitter Post to Plurk Post to Yahoo Buzz Post to Delicious Post to Digg Post to Facebook Post to MySpace Post to Ping.fm Post to Reddit Post to StumbleUpon

EContact
browser fav
page generated in 1447.978970 milliseconds

Why Google AdSense ads ?
compteur
 Ranking-Hits PageRank for this page