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
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.
Away.
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...
and that linear search is way too longCode:apstring words; temp>>words; while(!temp.eof()) { if(words==word) return true; temp>>words;
I need MONEY more than help with My C++ so yeah you get the idea
C notes preferably LOL
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.
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.
Mark Loeser
http://www.halcy0n.com
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 10:26 PM.
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
I need MONEY more than help with My C++ so yeah you get the idea
C notes preferably LOL
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
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
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
>>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]
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