File Searching

This is a discussion on File Searching within the C++ Programming forums, part of the General Programming Boards category; How do I Binary Search a file of unknown length. By the way I'm running on DOS so don't give ...

  1. #1
    phantobrain
    Guest

    Exclamation File Searching

    How do I Binary Search a file of unknown length. By the way I'm running on DOS so don't give me that fancy Visual C++ source code. Thanks

  2. #2
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    Visual C++ code is the same as any other code.

    You didn't really provide any information. That's important.

    Check www.aihorizon.com There might be something there that you'll like.
    Away.

  3. #3
    Registered User
    Join Date
    Jun 2003
    Posts
    18
    Seriously I need help with this as well because I'm working on boggle


    But I have all summer so yeah get to work


    This is what I have so far...
    Code:
      apstring words;
      temp>>words;
      while(!temp.eof())
      {
         if(words==word)
            return true;
         temp>>words;
    and that linear search is way too long
    I need MONEY more than help with My C++ so yeah you get the idea

    C notes preferably LOL

  4. #4
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    I'd suggest reading the entire file into memory (into say, a vector). Then, of course the lines of text must be sorted (for which the standard library provided capabilities), and then use a normal binary search algorithm.

    As you'd have to read the data in, your linear search is probably the fastest, unless you have to search multiple times... then I'd recommend reading it into memory.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  5. #5
    Registered User HaLCy0n's Avatar
    Join Date
    Mar 2003
    Posts
    77
    By the time you read them all in, sort them, and search, you could have just looked at them while reading them in. Your way of comparing them while reading them in is probably the fastest if you are just trying to find out if a word is in a file. Someone please correct me if I'm wrong.

  6. #6
    Cat
    Cat is offline
    Registered User
    Join Date
    May 2003
    Posts
    1,571
    Yes, if you're doing one search, no benefit. If you're doing multiple searches, big benefit.

    For text files, binary searches work very poorly; it's quite hard to accurately pull one off.

    If, however, you can pre-format the file such that a) it's alphabetized, and b) each string is of fixed length (e.g. make all strings 25 characters or something).

    In that case, you can write your own STL-compatible container (with random access iterators) and call teh STL's binary search algorithms.
    Last edited by Cat; 06-14-2003 at 11:26 PM.

  7. #7
    Registered User
    Join Date
    Jun 2003
    Posts
    18

    Exclamation

    No the problem I'm haveing is I want to binary search a file of unknown length case in point there are more 'S's than 'Z's so I want to effectively use my O(log N) of a binary search

    However I'm not quite that enthralled in doing a binary search
    Code:
       char strword[17];  //max is a 16 letter word
       strcpy(strword,word.c_str());
       strlwr(strword);
       word=strword;
       char let=word[0];
       if(let>'z' && let<'a')
       {
          cerr<<"That isn't a letter";
          return false;
       }
       ifstream temp;
    
    
       if(let=='a')
          temp.open("C:\mydocu~1\david\school\A.dc",ios::in);
       if(let=='b')
          temp.open("C:\mydocu~1\david\school\B.dc",ios::in);
       if(let=='c')
    /*...*/
    Now then I have this at the end
    Code:
       apstring words;
       getline(temp,words);
       while(!temp.eof())
       {
       }
       temp.close();
       return false;
    And i don't know what to put in the loop
    So please help if you dare
    I need MONEY more than help with My C++ so yeah you get the idea

    C notes preferably LOL

  8. #8
    Registered User
    Join Date
    Jun 2003
    Posts
    18
    By the way I did do the read into vector method first but I overloaded the memory stack


    But i guess you would have know that do to the fact you are a master toaster
    I need MONEY more than help with My C++ so yeah you get the idea

    C notes preferably LOL

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    What compiler do you use? You should replace apstring by std::string (if you are allowed to).
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  10. #10
    Registered User
    Join Date
    Jun 2003
    Posts
    18
    I guess you didn't realize the Unknown part. Is there a function to return the number of 'returns' in a file?

    Because that would be the length of the file.

    This is for boggle and I don't want to work much more onit
    I need MONEY more than help with My C++ so yeah you get the idea

    C notes preferably LOL

  11. #11
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    >>Is there a function to return the number of 'returns' in a file?<<
    No, I don't believe so. Just write your own instead.

    >>I don't want to work much more onit<<
    Good luck then
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  12. #12
    Registered User
    Join Date
    Jun 2003
    Posts
    18

    No More Need

    I finally got it to work so there will be no more need for any help and thanks a lot
    I need MONEY more than help with My C++ so yeah you get the idea

    C notes preferably LOL

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Data Structure Eror
    By prominababy in forum C Programming
    Replies: 3
    Last Post: 01-06-2009, 09:35 AM
  2. gcc link external library
    By spank in forum C Programming
    Replies: 6
    Last Post: 08-08-2007, 04:44 PM
  3. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  4. Possible circular definition with singleton objects
    By techrolla in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2004, 10:46 AM
  5. Need a suggestion on a school project..
    By Screwz Luse in forum C Programming
    Replies: 5
    Last Post: 11-27-2001, 02:58 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21