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
Printable View
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
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.
Seriously I need help with this as well because I'm working on boggle
But I have all summer so yeah get to work
:D
This is what I have so far...
and that linear search is way too longCode:
apstring words;
temp>>words;
while(!temp.eof())
{
if(words==word)
return true;
temp>>words;
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.
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.
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.
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
Now then I have this at the endCode: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')
/*...*/
And i don't know what to put in the loopCode:apstring words;
getline(temp,words);
while(!temp.eof())
{
}
temp.close();
return false;
So please help if you dare
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
What compiler do you use? You should replace apstring by std::string (if you are allowed to).
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
>>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 :D
I finally got it to work so there will be no more need for any help and thanks a lot