#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

#### Categories

Welcome to the new platform of Programmers Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use it's exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

• Posts: 9Member
This task is proving I know very little about programming. What am I doing wrong?
I'm using Turbo Pascal 1.5 for Windows and I don't think the compilor I am using supports the Break command. When I remove the Break, the program runs but it doesn't do what it is supposed to. If I enter "1" as the Person ID, "1 not found!" is displayed and when I enter "2" or any number above 1, the program seems like it freezes (it takes up 99% CPU Usage).

At the moment, my text file is populated with the following data:

[code]1 John Smith 123 Fake Street (11111) 111111
2 Pat Evans 31 Albert Square (22222) 222222[/code]

The code:
[code]Program Search;

Uses
WinCrt;

Var
f: Text;
i: Integer;
StringArray: Array[0..20] of String;
ArrayLength: Integer;
Low, Mid, High: Integer;
Result: Integer;
SearchValue: String;

Begin
assign(f, 'filename.txt');
reset(f);
i := 0;
while not eof(f) do
begin

write('Enter Person ID to see contact details: ');

inc(i);
Low := 0;
High := Length(StringArray[i])-1;
Result := -1;
if StringArray[Low] = SearchValue then
Result := Low
else if StringArray[High] = SearchValue then
Result := High
else while (Low <> High) and (Low+1 <> High) do
begin
Mid := (High-Low) div 2 + Low;
if StringArray[Mid] = SearchValue then
begin
Result := Mid;
Break;
end else if StringArray[Mid] > SearchValue then
High := Mid
else
Low := Mid;
end;
if StringArray[Low] = SearchValue then
Result := Low
else if StringArray[High] = SearchValue then
Result := High;
if Result = -1 then
else
writeln(SearchValue+' has an index of ',Result);
end;
Close(f);
ArrayLength := i;
End.[/code]
· ·
• Posts: 6,349Member
: This task is proving I know very little about programming. What am I
: doing wrong?
: I'm using Turbo Pascal 1.5 for Windows and I don't think the
: compilor I am using supports the Break command. When I remove the
: Break, the program runs but it doesn't do what it is supposed to. If
: I enter "1" as the Person ID, "1 not found!" is displayed and when I
: enter "2" or any number above 1, the program seems like it freezes
: (it takes up 99% CPU Usage).
:
: At the moment, my text file is populated with the following data:
:
: [code]: 1 John Smith 123 Fake Street (11111) 111111
: 2 Pat Evans 31 Albert Square (22222) 222222[/code]:
:
:
: The code:
: [code]: Program Search;
:
: Uses
: WinCrt;
:
: Var
: f: Text;
: i: Integer;
: StringArray: Array[0..20] of String;
: ArrayLength: Integer;
: Low, Mid, High: Integer;
: Result: Integer;
: SearchValue: String;
:
: Begin
: assign(f, 'filename.txt');
: reset(f);
: i := 0;
: while not eof(f) do
: begin
:
: write('Enter Person ID to see contact details: ');
:
: inc(i);
: Low := 0;
: High := Length(StringArray[i])-1;
: Result := -1;
: if StringArray[Low] = SearchValue then
: Result := Low
: else if StringArray[High] = SearchValue then
: Result := High
: else while (Low <> High) and (Low+1 <> High) do
: begin
: Mid := (High-Low) div 2 + Low;
: if StringArray[Mid] = SearchValue then
: begin
: Result := Mid;
: Break;
: end else if StringArray[Mid] > SearchValue then
: High := Mid
: else
: Low := Mid;
: end;
: if StringArray[Low] = SearchValue then
: Result := Low
: else if StringArray[High] = SearchValue then
: Result := High;
: if Result = -1 then
: else
: writeln(SearchValue+' has an index of ',Result);
: end;
: Close(f);
: ArrayLength := i;
: End.[/code]:
:
The Break is necessary to speed up the algorithm. See http://www.programmersheaven.com/mb/pasprog/370952/371008/ReadMessage.aspx?S=B20000#371008 for an alternative.
· ·
• Posts: 9Member
: The Break is necessary to speed up the algorithm. See
: .aspx?S=B20000#371008 for an alternative.

Using GoTo hasn't made any difference - the program behaves in the same way if the Break command was not used. And the program does not work. I can type any number equal to or below 1 and "n not found!" is displayed. If I type a number greater than 1 the program consumes a lot of CPU usage.

Here's teh code:

[code]Program Search;

Uses
WinCrt;

Var
f: Text;
i: Integer;
StringArray: Array[0..20] of String;
ArrayLength: Integer;
Low, Mid, High: Integer;
Result: Integer;
SearchValue: String;

Label
Break;

Begin
assign(f, 'filename.txt');
reset(f);
i := 0;
while not eof(f) do
begin

write('Enter Person ID to see contact details: ');

inc(i);

Low := 0;
High := Length(StringArray[i])-1;
Result := -1;
if StringArray[Low] = SearchValue then
Result := Low
else if StringArray[High] = SearchValue then
Result := High
else while (Low <> High) and (Low+1 <> High) do
begin
Mid := (High-Low) div 2 + Low;
if StringArray[Mid] = SearchValue then
begin
Result := Mid;
Goto Break
end else if StringArray[Mid] > SearchValue then
High := Mid
else
Low := Mid;
end;
if StringArray[Low] = SearchValue then
Result := Low
else if StringArray[High] = SearchValue then
Result := High;
if Result = -1 then
else
writeln(SearchValue+' has an index of ',Result);

end;
Break:
Close(f);
ArrayLength := i;
End.[/code]
· ·
• Posts: 6,349Member
: : The Break is necessary to speed up the algorithm. See
: : .aspx?S=B20000#371008 for an alternative.
:
: Using GoTo hasn't made any difference - the program behaves in the
: same way if the Break command was not used. And the program does not
: work. I can type any number equal to or below 1 and "n not found!"
: is displayed. If I type a number greater than 1 the program consumes
: a lot of CPU usage.
:
: Here's teh code:
:
: [code]: Program Search;
:
: Uses
: WinCrt;
:
: Var
: f: Text;
: i: Integer;
: StringArray: Array[0..20] of String;
: ArrayLength: Integer;
: Low, Mid, High: Integer;
: Result: Integer;
: SearchValue: String;
:
: Label
: Break;
:
: Begin
: assign(f, 'filename.txt');
: reset(f);
: i := 0;
: while not eof(f) do
: begin
:
: write('Enter Person ID to see contact details: ');
:
: inc(i);
:
: Low := 0;
: High := Length(StringArray[i])-1;
: Result := -1;
: if StringArray[Low] = SearchValue then
: Result := Low
: else if StringArray[High] = SearchValue then
: Result := High
: else while (Low <> High) and (Low+1 <> High) do
: begin
: Mid := (High-Low) div 2 + Low;
: if StringArray[Mid] = SearchValue then
: begin
: Result := Mid;
: Goto Break
: end else if StringArray[Mid] > SearchValue then
: High := Mid
: else
: Low := Mid;
: end;
: if StringArray[Low] = SearchValue then
: Result := Low
: else if StringArray[High] = SearchValue then
: Result := High;
: if Result = -1 then
: else
: writeln(SearchValue+' has an index of ',Result);
:
: end;
: Break:
: Close(f);
: ArrayLength := i;
: End.[/code]:
:
Can you figure out why the program doesn't work? You should be able to since figuring out how the program works is your goal.
· ·
• Posts: 9Member
: Can you figure out why the program doesn't work? You should be able
: to since figuring out how the program works is your goal.

i'll try. thanks for all your help :)
· ·
• Posts: 438Member
: : Can you figure out why the program doesn't work? You should be able
: : to since figuring out how the program works is your goal.
:
: i'll try. thanks for all your help :)
:
[blue]You need to read the entire file into your array before you begin the search.[/blue]
[code]
Begin
assign(f, 'filename.txt');
reset(f);
i := 0;
while not eof(f) do
begin
if i > 20 then begin
writeln ('File is too big to fit in memory.') ;
close(f) ;
halt
end ;
i := i + 1
end ;
close(f) ; [red]{ the entire file is now in memory }[/red]

ArrayLength := i - 1 ; [red]{ index of the last record }[/red]

write('Enter Person ID to see contact details: ');
[red]{
}[/red]

[/code]
· ·
• Posts: 438Member
: : Can you figure out why the program doesn't work? You should be able
: : to since figuring out how the program works is your goal.
:
: i'll try. thanks for all your help :)
:
[blue]
Database type records stored in text files are more than likely column sensitive, as in the following. The items in red are for reference only and are not part of the file.
[/blue]
[code]
[red]
1 2 3 4 5
12345678901234567890123456789012345678901234567890[/red]
[red] 0[/red] 101 John Smith 123 Fake Street (11111) 111111
[red] 1[/red] 102 Pat Evans 31 Albert Square (22222) 222222
[red] 2[/red] 103 Annette Funicello 125 Hollywood Blvd (33333) 333333
[red] 3[/red] 105 Sandra Dee 501 Mulholland Road (44444) 444444
[red] 4[/red] 107 Tuesday Weld 777 Magnificent Ave (55555) 555555
[red] 5[/red] 111 Carol Lynley 123 Blue Demim (66666) 666666
[red] 6[/red] 113 Hayley Mills 1001 Pollyanne Ave (77777) 777777
[red] 7[/red] 117 Deborah Walley 2 Hawaiian (88888) 888888
[red] 8[/red] 123 Sally Field 1 Smoky Road (99999) 999999
[red] 9[/red] 129 Frankie Avalon 999 Beachfront (11111) 222222
[red]10[/red] 131 Fabian Forte 500 Fileball (22222) 333333
[red]11[/red] 137 Elvis Presley 1 Graceland (33333) 444444
[red]12[/red] 141 Troy Donahue 9 Summer Place (44444) 555555
[red]13[/red] 147 Douglas McClure 77 Sunset Strip (55555) 666666
[red]14[/red] 153 Salvatore Mineo 111 Drummer (66666) 777777
[/code]
[blue]
The numbers in red on the left are the record numbers and, as I said, are not part of the file. PersonNumber is stored in columns 1 .. 3; FirstName is in columns 5 .. 14, etc. Make sure your data elements begin in the correct column.

When using binary search it is absolutely vital that the file be sorted in "key field order", the key field in this case being PersonNumber in columns 1 .. 3. Note that this is a substring and not actually a number. If the file is not sorted then the search will almost certainly fail.

Comparisons between SearchValue and StringArray[i] should be between the first three characters only. E.g.,
[/blue]
[code]
if Copy(StringArray[i],1,3) = SearchValue then
[/code]
[blue]
StringArray[i] will never equal SearchValue unless you type in an entire copy of the record you are searching for (tedious, error prone, and if you already have all that data why are you searching the file).
[/blue]
· ·
• Posts: 9Member
Thank you for replying. I think the program stops responding because a loop keeps running. I think I am using the goto incorrectly? I know the file is being read because I can call specific elements of the array and it works. It's just the binary search I'm having problems with.

I don't know what you meant by the comparison between SearchValue and StringArray[i].

[code]Program Search;

Uses
WinCrt;

Var
f: Text;
i: Integer;
StringArray: Array[0..20] of String;
ArrayLength: Integer;
Low, Mid, High: Integer;
Result: Integer;
SearchValue: String;

Label
Break;

Begin
assign(f, 'filename.txt');
reset(f);
i := 0;
while not eof(f) do
begin
if i > 20 then begin
writeln ('File is too big to fit in memory.');
close(f);
halt
end ;
i := i + 1;
end;
close(f);

ArrayLength := i - 1;

write('Enter Person ID to see contact details: ');

Low := 0;
High := Length(StringArray[i])-1;
Result := -1;

if StringArray[Low] = SearchValue then
Result := Low
else
if StringArray[High] = SearchValue then
Result := High
else
while (Low <> High) and (Low+1 <> High) do
begin
Mid := (High-Low) div 2 + Low;
if StringArray[Mid] = SearchValue then
begin
Result := Mid;
Goto Break;
end
else if StringArray[Mid] > SearchValue then
High := Mid
else
Low := Mid;
end;

[b]Break:[/b]

if StringArray[Low] = SearchValue then
Result := Low
else if StringArray[High] = SearchValue then
Result := High;
if Result = -1 then
else
writeln(SearchValue+' has an index of ',Result);
End.[/code]
· ·
• Posts: 6,349Member
: Thank you for replying. I think the program stops responding because
: a loop keeps running. I think I am using the goto incorrectly? I
: know the file is being read because I can call specific elements of
: the array and it works. It's just the binary search I'm having
: problems with.
:
: I don't know what you meant by the comparison between SearchValue
: and StringArray[i].
:
: [code]: Program Search;
:
: Uses
: WinCrt;
:
: Var
: f: Text;
: i: Integer;
: StringArray: Array[0..20] of String;
: ArrayLength: Integer;
: Low, Mid, High: Integer;
: Result: Integer;
: SearchValue: String;
:
: Label
: Break;
:
: Begin
: assign(f, 'filename.txt');
: reset(f);
: i := 0;
: while not eof(f) do
: begin
: if i > 20 then begin
: writeln ('File is too big to fit in memory.');
: close(f);
: halt
: end ;
: i := i + 1;
: end;
: close(f);
:
: ArrayLength := i - 1;
:
: write('Enter Person ID to see contact details: ');
:
: Low := 0;
: High := Length(StringArray[i])-1;
: Result := -1;
:
: if StringArray[Low] = SearchValue then
: Result := Low
: else
: if StringArray[High] = SearchValue then
: Result := High
: else
: while (Low <> High) and (Low+1 <> High) do
: begin
: Mid := (High-Low) div 2 + Low;
: if StringArray[Mid] = SearchValue then
: begin
: Result := Mid;
: Goto Break;
: end
: else if StringArray[Mid] [b][red]<[/red][/b] SearchValue then
: High := Mid
: else
: Low := Mid;
: end;
:
: [b]Break:[/b]
:
: if StringArray[Low] = SearchValue then
: Result := Low
: else if StringArray[High] = SearchValue then
: Result := High;
: if Result = -1 then
: else
: writeln(SearchValue+' has an index of ',Result);
: End.[/code]:
:
One of the comparisons (in red above) was incorrect. That broke the binary search. The red one is the corrected one. With "the comparison between SearchValue and StringArray[i]" is meant, any statement which takes the value stored in SearchValue and takes the value stored in the i-th element of the StringArray; and then compares (using one of the =, <, <=, >, >=, <> operators) those values with eachother. There are several of those in the code above.
· ·
• Posts: 438Member
: Thank you for replying. I think the program stops responding because
: a loop keeps running. I think I am using the goto incorrectly? I
: know the file is being read because I can call specific elements of
: the array and it works. It's just the binary search I'm having
: problems with.
:

I've gone over your program several times and I can't figure out how it is supposed to work. I believe that the problem is that your search algorithm is simply wrong. It's more complex than it needs to be and (sorry) it simply does not work. I think your attempt to use this code has lead to more confusion than enlightenment.

The following makes use of an algorithm in Knuth's THE ART OF COMPUTER PROGRAMMING.

: I don't know what you meant by the comparison between SearchValue
: and StringArray[i].
:

This program assumes that the first three characters in each record make up the "key", i.e., the sample of data that you are searching for. It also assumes that the operator will enter exactly three characters (SearchValue) when prompted, no more, no less. Anything else and the program will not work.

Once the operator has entered SearchValue, those three characters have to be compared with the first three characters of StringArray[i] that is being examined. We extract the first three characters and store them in the string "Key". This is done in the statement
[code]
Key := Copy(StringArray[i], 1, 3) ;
[/code]
SearchValue is then compared to key (twice) in the statement
[code]
if SearchValue < Key then
High := i - 1
else if SearchValue > Key then
Low := i + 1
else begin
writeln(StringArray[i]) ;
Halt
end
[/code]
If each character in SearchValue is the same as the corresponding character in Key then the two are equal; if not then which is greatest is determined by the ascii representation of the first mismatched characters. The statement tests for SearchValue < Key, SearchValue > Key. The only other possibility, SearchValue = Key, becomes the [b]else[/b] part (and signals a successful end of the search).
[code]
Program Search;

Var
f : Text ;
i : Integer ;
StringArray : Array[0 .. 20] of String ;
Low, High : Integer ;
SearchValue : String ;
Key : String ;

Begin
{
}
assign(f, 'filename.txt') ;
reset(f) ;
i := 0 ;
while not eof(f) do
begin
if i > 20 then begin
writeln ('File is too big to fit in memory.') ;
close(f) ;
halt
end ;
i := i + 1
end ;
close(f) ;

write('Enter Person ID to see contact details: ') ;
{
binary search algorithm from
Knuth's THE ART OF COMPUTER PROGRAMMING
Vol 3, 2nd edition, page 410
}
Low := 0 ;
High := i - 1 ;

while High >= Low do begin [red]{ High < Low means the search has failed }[/red]
{
at this point we know that if SearchValue is in the
array it satisfies

Key[Low] <= SearchValue <= Key[High]
}
i := (Low + High) div 2 ; { get midpoint }
{
Compare
}
Key := Copy(StringArray[i], 1, 3) ;
if SearchValue < Key then
High := i - 1
else if SearchValue > Key then
Low := i + 1
else begin [red]{ Success! Search = Key - the only other possibility }[/red]
writeln(StringArray[i]) ;
Halt
end
end ;
{
Failure
}