Address Book Search Program

2»

Comments

  • : : 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 ;
    readln(f, StringArray[i]);
    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: ');
    readln(SearchValue);
    [red]{
    now start your search
    }[/red]


    [/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.
    :
    : 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]
  • 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 ;
    readln(f, StringArray[i]);
    i := i + 1;
    end;
    close(f);

    ArrayLength := i - 1;

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

    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
    writeln(SearchValue+' not found!')
    else
    writeln(SearchValue+' has an index of ',Result);
    End.[/code]
  • : 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 ;
    : readln(f, StringArray[i]);
    : i := i + 1;
    : end;
    : close(f);
    :
    : ArrayLength := i - 1;
    :
    : write('Enter Person ID to see contact details: ');
    : readln(SearchValue);
    :
    : 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
    : writeln(SearchValue+' not found!')
    : 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.
  • : 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
    {
    load file into memory
    }
    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 ;
    readln(f, StringArray[i]) ;
    i := i + 1
    end ;
    close(f) ;

    write('Enter Person ID to see contact details: ') ;
    readln(SearchValue) ;
    {
    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
    }
    writeln(SearchValue + ' not found!')

    End.
    [/code]

    I've tested this program using the data I previously posted and it seems to work.

    Actor

  • Thanks! The code was easy to understand. I have another question - In the last line of the program ([b]writeln(SearchValue + ' not found!')[/b]), you have used '+'. I've been taught to concatenate using a comma. Is there a right way of using +'s and commas or is it just for preference?
  • : Thanks! The code was easy to understand. I have another question -
    : In the last line of the program ([b]writeln(SearchValue + ' not
    : found!')[/b]), you have used '+'. I've been taught to concatenate
    : using a comma. Is there a right way of using +'s and commas or is it
    : just for preference?
    :

    I would say it's just a preference. Either one works and, as far as I know, the output is always the same, although it's possible that is some cases there may be a slight difference in what gets output.
  • : : Thanks! The code was easy to understand. I have another question -
    : : In the last line of the program ([b]writeln(SearchValue + ' not
    : : found!')[/b]), you have used '+'. I've been taught to concatenate
    : : using a comma. Is there a right way of using +'s and commas or is it
    : : just for preference?
    : :
    :
    : I would say it's just a preference. Either one works and, as far as
    : I know, the output is always the same, although it's possible that
    : is some cases there may be a slight difference in what gets output.
    :
    Comma's only work in readln() and writeln() due to some compiler-magic. In all other cases you need to use the +. For example:
    [code]
    procedure MyWrite(TextToWrite: string);
    begin
    writeln(TextToWrite);
    end;

    begin
    MyWrite('Hello', ' World'); { Compiler error }
    MyWrite('Hello' + ' World'); { Works }
    end.
    [/code]
    This is because readln() and writeln() can have any number of parameters of nearly any type, while self created procedures have the parameters and their types specified at compile-time.
  • : : : Thanks! The code was easy to understand. I have another question -
    : : : In the last line of the program ([b]writeln(SearchValue + ' not
    : : : found!')[/b]), you have used '+'. I've been taught to concatenate
    : : : using a comma. Is there a right way of using +'s and commas or is it
    : : : just for preference?
    : : :
    : :
    : : I would say it's just a preference. Either one works and, as far as
    : : I know, the output is always the same, although it's possible that
    : : is some cases there may be a slight difference in what gets output.
    : :
    : Comma's only work in readln() and writeln()
    [blue]
    I assumed that concatenation in writeln() was the context of the question.
    [/blue]
    : due to some
    : compiler-magic. In all other cases you need to use the +. For
    : example:
    : [code]:
    : procedure MyWrite(TextToWrite: string);
    : begin
    : writeln(TextToWrite);
    : end;
    :
    : begin
    : MyWrite('Hello', ' World'); { Compiler error }
    : MyWrite('Hello' + ' World'); { Works }
    : end.
    : [/code]:
    : This is because readln() and writeln() can have any number of
    : parameters of nearly any type,
    [blue]
    Actually both take parameters of only a few types: integer, char, real and their various cousins (byte, word, short, etc). Neither will handle arrays (except for strings) nor user defined types (other than enumerations). Also, I don't think you can use + in readln. Readln(FirstName + LastName) would not work, and even it did, it would not be good programming style.
    [/blue]



  • [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 ;
    readln(f, StringArray[i]) ;
    i := i + 1
    end ;
    close(f) ;
    [red]{
    Note that, if the file loads successfully and the program reaches
    this point, [b]i[/b] points to the array member that immediately
    follows the last record loaded, i.e., [b]i[/b] points to garbage.
    }[/red]
    ArrayLength := i - 1 ;

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

    Low := 0 ;
    High := Length(StringArray[i]) - 1 ;
    [red]{
    This is the first error in the program. [b]High[/b] should be
    set to [b]ArrayLength[/b]. Instead it is set to 1 less than the
    length of [b]StringArray[i][/b]. But [b]StringArray[i][/b], as
    pointed out above, has not been initialized, and so is garbage.

    Actually, Borland Pascal will initialize the string to a nul
    string whose length is zero, meaning [b]High[/b] will be -1
    }[/red]
    Result := -1 ;

    [red]{
    The programmer apparently does not expect his algorithm to
    handle boundary cases and so makes provision in the following
    to make them special cases. Actually, the algorithm will
    handle the boundary cases, so the complexity of the program is
    increased needlessly.
    }[/red]
    if StringArray[Low] = SearchValue then
    [red]{
    This expression is very unlikely to ever evaluate to TRUE.
    [b]SearchValue[/b] is probably entered as the three character
    (or whatever length) string that makes up the searched for key.
    On the other hand [b]StringArray[/b] is the entire record, not
    just the key.
    }[/red]
    Result := Low
    else
    if StringArray[High] = SearchValue then
    [red]{
    Again the expression is unlikely to ever evaluate to TRUE.
    However, in addition we note that if [b]High[/b] is initially
    equal to -1 then the index is outside its range. If range
    checking is ON then we can expect a run time error.
    }[/red]
    Result := High
    else
    [red]{
    note that, going into the loop, [b]Low[/b] = 0 and [b]High[/b] = -1
    }[/red]
    while (Low <> High) and (Low+1 <> High) do
    [red]{
    A logical error!
    Both [b]Low = High[/b] and [b]Low+1 = High[/b] are valid
    conditions and should not terminate the loop. The correct
    test is [b]Low <= High[/b]
    }[/red]
    begin
    Mid := (High - Low) div 2 + Low ; [red]{ Mid = 0 }[/red]
    if StringArray[Mid] = SearchValue then [red]{ test fails }[/red]
    begin
    Result := Mid ;
    Goto Break ;
    end
    else if StringArray[Mid] < SearchValue then [red]{ test fails }[/red]
    High := Mid
    else
    Low := Mid ; [red]{ but [b]Mid[/b] = 0 so the value of
    [b]Low[/b] remains unchanged and we go
    into an infinite loop!!!
    }[/red]
    end ;

    Break:

    if StringArray[Low] = SearchValue then
    Result := Low
    else if StringArray[High] = SearchValue then
    Result := High ;
    if Result = -1 then
    writeln(SearchValue+' not found!')
    else
    writeln(SearchValue+' has an index of ',Result) ;
    End.
    [/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
    : if i > 20 then begin
    : writeln ('File is too big to fit in memory.') ;
    : close(f) ;
    : halt
    : end ;
    : readln(f, StringArray[i]) ;
    : i := i + 1
    : end ;
    : close(f) ;
    : [red]{
    : Note that, if the file loads successfully and the program reaches
    : this point, [b]i[/b] points to the array member that immediately
    : follows the last record loaded, i.e., [b]i[/b] points to garbage.
    : }[/red]
    : ArrayLength := i - 1 ;
    :
    : write('Enter Person ID to see contact details: ') ;
    : readln(SearchValue) ;
    :
    : Low := 0 ;
    : High := Length(StringArray[i]) - 1 ;
    : [red]{
    : This is the first error in the program. [b]High[/b] should be
    : set to [b]ArrayLength[/b]. Instead it is set to 1 less than the
    : length of [b]StringArray[i][/b]. But [b]StringArray[i][/b], as
    : pointed out above, has not been initialized, and so is garbage.
    :
    : Actually, Borland Pascal will initialize the string to a nul
    : string whose length is zero, meaning [b]High[/b] will be -1
    : }[/red]
    [blue]
    { This line was changed from my original program. The original read:
    [b]High := Length(StringArray) - 1 ;[/b]
    which points to the last valid index of the 0-indexed array. In that case
    the High is the highest index the array can have: 20. }
    [/blue]
    : Result := -1 ;
    :
    : [red]{
    : The programmer apparently does not expect his algorithm to
    : handle boundary cases and so makes provision in the following
    : to make them special cases. Actually, the algorithm will
    : handle the boundary cases, so the complexity of the program is
    : increased needlessly.
    : }[/red]
    [blue]
    { True: the algorithm handles the boundary cases. I've inserted these to
    speed up the algorithm. This way you don't need to perform a large number
    of iterations inside the loop if you search for the first or last element. }
    [/blue]
    : if StringArray[Low] = SearchValue then
    : [red]{
    : This expression is very unlikely to ever evaluate to TRUE.
    : [b]SearchValue[/b] is probably entered as the three character
    : (or whatever length) string that makes up the searched for key.
    : On the other hand [b]StringArray[/b] is the entire record, not
    : just the key.
    : }[/red]
    [blue]
    { Again true, but instead of having the algorithm's complexity increased
    by handling a case-insensitive substring comparison, I just took a simple
    string-comparison. Usually the comparison is done in a function and is
    based on the data-structure. Since I didn't know the internal
    data-structure (strings with substring keys, records, sql-statements, etc.)
    I took the most basic comparison. }
    [/blue]
    : Result := Low
    : else
    : if StringArray[High] = SearchValue then
    : [red]{
    : Again the expression is unlikely to ever evaluate to TRUE.
    : However, in addition we note that if [b]High[/b] is initially
    : equal to -1 then the index is outside its range. If range
    : checking is ON then we can expect a run time error.
    : }[/red]
    : Result := High
    : else
    : [red]{
    : note that, going into the loop, [b]Low[/b] = 0 and [b]High[/b] = -1
    : }[/red]
    [blue]{ See note about High. In the original code: Low = 0 and High = 20, when going into the loop. }[/blue]
    : while (Low <> High) and (Low+1 <> High) do
    : [red]{
    : A logical error!
    : Both [b]Low = High[/b] and [b]Low+1 = High[/b] are valid
    : conditions and should not terminate the loop. The correct
    : test is [b]Low <= High[/b]
    [blue]{
    If Low = High, then Mid = Low = High. If the searchstring doesn't match
    StringArray[mid], then you will have an infinite loop, because Mid will never change.
    If Low+1 = High, then Mid = Low. If the searchstring doesn't match
    StringArray[mid], then you will have an infinite loop, because Mid will never change.
    Since Low can never be greater than High, the condition Low <= High will
    create an infinite loop. Low will always be set to Mid, as will High. This
    means that Mid will always be between Low and High. These two statements
    will never cause Low to be raised above High.
    }[/blue]
    : }[/red]
    : begin
    : Mid := (High - Low) div 2 + Low ; [red]{ Mid = 0 }[/red]
    [blue]{ See note about Low and High} [/blue]
    : if StringArray[Mid] = SearchValue then [red]{ test fails }[/red]
    [blue]{ See note about Low and High} [/blue]
    : begin
    : Result := Mid ;
    : Goto Break ;
    : end
    : else if StringArray[Mid] < SearchValue then [red]{ test fails }[/red]
    [blue]{ See note about Low and High} [/blue]
    : High := Mid
    : else
    : Low := Mid ; [red]{ but [b]Mid[/b] = 0 so the value of
    : [b]Low[/b] remains unchanged and we go
    : into an infinite loop!!!
    : }[/red]
    [blue]{ See note about Low and High} [/blue]
    : end ;
    :
    : Break:
    :
    : if StringArray[Low] = SearchValue then
    : Result := Low
    : else if StringArray[High] = SearchValue then
    : Result := High ;
    : if Result = -1 then
    : writeln(SearchValue+' not found!')
    : else
    : writeln(SearchValue+' has an index of ',Result) ;
    : End.
    : [/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
    : : if i > 20 then begin
    : : writeln ('File is too big to fit in memory.') ;
    : : close(f) ;
    : : halt
    : : end ;
    : : readln(f, StringArray[i]) ;
    : : i := i + 1
    : : end ;
    : : close(f) ;
    : : {
    : : Note that, if the file loads successfully and the program reaches
    : : this point, [b]i[/b] points to the array member that immediately
    : : follows the last record loaded, i.e., [b]i[/b] points to garbage.
    : : }
    : : ArrayLength := i - 1 ;
    : :
    : : write('Enter Person ID to see contact details: ') ;
    : : readln(SearchValue) ;
    : :
    : : Low := 0 ;
    : : High := Length(StringArray[i]) - 1 ;
    : : {
    : : This is the first error in the program. [b]High[/b] should be
    : : set to [b]ArrayLength[/b]. Instead it is set to 1 less than the
    : : length of [b]StringArray[i][/b]. But [b]StringArray[i][/b], as
    : : pointed out above, has not been initialized, and so is garbage.
    : :
    : : Actually, Borland Pascal will initialize the string to a nul
    : : string whose length is zero, meaning [b]High[/b] will be -1
    : : }
    : [blue]
    : { This line was changed from my original program. The original read:
    : [b]High := Length(StringArray) - 1 ;[/b]
    : which points to the last valid index of the 0-indexed array. In that case
    : the High is the highest index the array can have: 20. }
    : [/blue]
    [red]{
    Who changed it? And why?

    This may be implementation dependent but, in Borland
    Pascal, [b]Length[/b] takes an argument of type
    [b]String[/b] and returns the length of that string.
    [b]StringArray[/b] without an index is not a string.
    I suspect whoever changed it did so because they were
    getting a compile time error (type mismatch).

    Even if it worked as you say and [b]High[/b] becomes
    the highest index of the array, this is not what is
    needed. If the file does not fill the array then any
    elements of the array beyond the last one loaded from
    the file will be garbage. An absolute requirement for
    binary search to work is that the array be sorted. If
    any elements are garbage then the array is not sorted.
    [b]High[/b] needs to be set to the last index loaded,
    not the last index possible.
    }[/red]
    : : Result := -1 ;
    : :
    : : {
    : : The programmer apparently does not expect his algorithm to
    : : handle boundary cases and so makes provision in the following
    : : to make them special cases. Actually, the algorithm will
    : : handle the boundary cases, so the complexity of the program is
    : : increased needlessly.
    : : }
    : [blue]
    : { True: the algorithm handles the boundary cases. I've inserted these to
    : speed up the algorithm. This way you don't need to perform a large number
    : of iterations inside the loop if you search for the first or last element. }
    [red]{
    Make it correct before you make it faster. Since the
    program is not correct at this point any attempt to
    "speed up the algorithm" is premature. Furthermore, as
    Kernighan and Plauger point out in [italic]Elements of
    Programming Style[/italic], programmers' conceptions of
    what will speed up the program often are not true. Testing
    is the only reliable way to find out. In this particular
    case the chance that the desired element will exist at the
    boundary is small, particularly if the program is later
    modified to handle large files, so any hoped for increase in
    speed is elusive and the increased complexity not justified.

    K&P wrote [italic]Elements of Programming Style[/italic] over
    30 years ago and it surprises me that today's programmers
    so often fail to heed their advise. Correctness and
    readability (style) take a back seat to speed and size.
    Every programmer should read and understand EOPS. True, the
    examples are in Fortran and PL/1, but the effort will pay
    dividends.
    }[/red]
    : [/blue]
    : : if StringArray[Low] = SearchValue then
    : : {
    : : This expression is very unlikely to ever evaluate to TRUE.
    : : [b]SearchValue[/b] is probably entered as the three character
    : : (or whatever length) string that makes up the searched for key.
    : : On the other hand [b]StringArray[/b] is the entire record, not
    : : just the key.
    : : }
    : [blue]
    : { Again true, but instead of having the algorithm's complexity increased
    : by handling a case-insensitive substring comparison, I just took a simple
    : string-comparison. Usually the comparison is done in a function and is
    : based on the data-structure. Since I didn't know the internal
    : data-structure (strings with substring keys, records, sql-statements, etc.)
    : I took the most basic comparison. }
    [red]{ Unfortunately the most basic comparison does not work. }[/red]
    : [/blue]
    : : Result := Low
    : : else
    : : if StringArray[High] = SearchValue then
    : : {
    : : Again the expression is unlikely to ever evaluate to TRUE.
    : : However, in addition we note that if [b]High[/b] is initially
    : : equal to -1 then the index is outside its range. If range
    : : checking is ON then we can expect a run time error.
    : : }
    : : Result := High
    : : else
    : : {
    : : note that, going into the loop, [b]Low[/b] = 0 and [b]High[/b] = -1
    : : }
    : [blue]{ See note about High. In the original code: Low = 0 and High = 20, when going into the loop. }[/blue]
    : : while (Low <> High) and (Low+1 <> High) do
    : : {
    : : A logical error!
    : : Both [b]Low = High[/b] and [b]Low+1 = High[/b] are valid
    : : conditions and should not terminate the loop. The correct
    : : test is [b]Low <= High[/b]
    : [blue]{
    : If Low = High, then Mid = Low = High. If the searchstring doesn't match
    : StringArray[mid], then you will have an infinite loop, because Mid will never change.
    : If Low+1 = High, then Mid = Low. If the searchstring doesn't match
    : StringArray[mid], then you will have an infinite loop, because Mid will never change.
    : Since Low can never be greater than High, the condition Low <= High will
    : create an infinite loop. Low will always be set to Mid, as will High. This
    : means that Mid will always be between Low and High. These two statements
    : will never cause Low to be raised above High.
    : }[/blue]
    [red]{ Oops! I missed two additional errors in the code. See below. }[/red]
    : : }
    : : begin
    : : Mid := (High - Low) div 2 + Low ; { Mid = 0 }
    : [blue]{ See note about Low and High} [/blue]
    : : if StringArray[Mid] = SearchValue then { test fails }
    : [blue]{ See note about Low and High} [/blue]
    : : begin
    : : Result := Mid ;
    : : Goto Break ;
    : : end
    : : else if StringArray[Mid] < SearchValue then { test fails }
    : [blue]{ See note about Low and High} [/blue]
    : : High := Mid [red]{ should be High := Mid - 1 }[/red]
    : : else
    : : Low := Mid ; [red]{ should be Low := Mid + 1
    with these two corrections my
    arguments concerning the tests
    for the while loop stand.
    }[/red]
    { but [b]Mid[/b] = 0 so the value of
    : : [b]Low[/b] remains unchanged and we go
    : : into an infinite loop!!!
    : : }
    : [blue]{ See note about Low and High} [/blue]
    : : end ;
    : :
    : : Break:
    : :
    : : if StringArray[Low] = SearchValue then
    : : Result := Low
    : : else if StringArray[High] = SearchValue then
    : : Result := High ;
    : : if Result = -1 then
    : : writeln(SearchValue+' not found!')
    : : else
    : : writeln(SearchValue+' has an index of ',Result) ;
    : : End.
    : : [/code]: :
    : :
    :

Sign In or Register to comment.

Howdy, Stranger!

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

Categories