spare Delphi 3 binary search class/unit anyone please?!

Dear Pandora.

I was wondering! Why not use a Balanced-tree or Hashing-tables
or something else, instead of a binary search ? Any
specific reason why you wan't to use "Binary Search" ?
Binary search is a slow and cumbersome routine, compared to
other more powerfull and efficient routines. I don't
think Delphi has any of those "in it" , however I
recomend that you try this PASCAL book out!
"Data structures and problem solving with turbo pascal"
ISBN : 0-8053-1217-X
Pascal is 99% Delphi, so it shouldn't be a problem
to code a unit. There are execellent examples with
full source, and very good comments and remarks -
proof of routines, lots of ADT's and "Big O" notations.
The book contains a lot of powerfull routines that you
can actually almost just type in!

If you don't want to use a book (books are SO RETRO ;-) )
then try out this http://sunsite.icm.edu.pl/delphi/
they have A LOT of delphi code there.

Best wishes!

GOMF

Williams2, you are too fast! (Though all it seems to do is read the code - where does it search for an item?)

Here is the answer I did. It searches for an item in the file using a comparison function you provide. It implements a standard binary search. This code guarantees at most log(base2)n disk reads to locate an item in the file...

Binary searches are OK if you will not be doing large numbers of them. And reading from the file enables arbitrary size files to be used...

Off the top of my head this code should do it. It compiles but I have not tested it.

Cheers,

Raymond.


type
  TCompareProc = function(a, b : string) : Integer; // (a<b) < 0, (a=b) = 0, (a > b) > 0

const
  Reclen = 20;

Function Find(const FName : TFileName;
              const S : String;
              Compare : TCompareProc) : Integer; // index of record, -1 if not found
var
  Start, middle, finish : integer;
  TheFile : File of byte;
  s1, s2, s3 : string;
  found : boolean;
  CompareResult : Integer;

function GetRecord(Index : Integer) : String;
begin
  Seek(TheFile, Index * RecLen);
  BlockRead(TheFile, Result, RecLen);
end;

begin
  Result := -1;
  Found := False;
  SetLength(s1, RecLen);
  SetLength(s2, RecLen);
  SetLength(s3, RecLen);
  assignfile(TheFile, FName);
  try
    reset(TheFile);
    try
      Start := 0;
      Finish := FileSize(TheFile) DIV RecLen - 1;
      s1 := GetRecord(start);
      s3 := GetRecord(finish);
      while not found and (Middle <> finish) do
      begin
        Middle := (Start + Finish) DIV 2;
        S2 := GetRecord(Middle);
        CompareResult := Compare(S2, S);
        if CompareResult = 0 then
          begin
            Found := True;
            Result := Middle;
          end
        else
          if CompareResult < 0 then
            begin
              Start := middle;
              S2 := s1;
            end
          else
            begin
              Finish := Middle;
              S2 := s3;
            end;
      end
    finally
      CloseFile(TheFile);
    end;
  except
    // handle exception here
  end;
end;

thanks for your help; I felt it could have been a little more modular (!) - cheeky aren't I!

I wanted to thank GOMF & rwilson too; because their advice was also invaluable - do u know any way of doing this please?
best wishes
P.

ahh; this seems to have done the trick!

I am confused. You accepted an answer that wasn't an answer to your question!

What was your real question then?

Raymond.

Raymond:

The guy doesn't want a BSP search tree, he wants an utility able to search and replace some specific matches in a file, such like end-of-line characters.

I know what you think :-) ..but since the guy needs a search in a binary file and not a binary search in a file, this could confuse the most, don't you think ?

Cheers,
Williams

Williams2: Stop smoking that weed! Pandora's question very specifically states that he/she wanted to do a binary search (as in locate a specific item using a binary search algorithm) in a text file. Pandora did NOT mention BSP (which, BTW, stand for Binary Space Partition trees), nor did Pandora mention that they wanted to search a binary (as in non-text) file.

Cheers,

Raymond.

I know what you mean, but how would you do an effiecient binary search in a file which is not sorted ?? I also read the context of his question and got a little confused, so I guessed he was looking for that kind of functionality.

The function identyfies a given separator in a large file, and pastes the contents between as lines in a stringgrid, this type of code is not trivial, but might be done faster, have you got any suggestions ?

Regards,
Williams

I assumed when Pandora said that she wanted to do a binary search that the file was sorted - perhaps I assumed too much (but I don't think so :-)

Raymond.

Just to clarify; yes I did want a binary search of a sorted file and yes, I apologise to Raymond his answer was actually more useful because it set me off on the right track (although doesn't quite work as the loop would get stuck!) - However the last time I used this site, i swear you could award points between respondents which is what i would have liked to do; this time i was only given the option of throwing it open to others or saying yes - in retrospect i should have thrown it open and so Raymond please accept my apologies; I'll remember you next time!

Raymond: I guess I owe you then..

Pandora: Thanks for clarifying this:

Williams2: Its nothing to worry about :-) :-) !

Cheers,

Raymond.