I've to make a function that checks if specific word exists in .bin file. I want to use Binary Search algorithm. Thing is, I've to read from .bin file, so I got confused (as there's no lines, right?). Function doesn't work for me. It says that 'specific word' (entered by user) doesn't exist, even though it does. Any help would be nice.
#include <iostream>
#include <string>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
const int buffer_size = 30;
void Create_Bin_File ()
{
ifstream fin ("example.txt");
ofstream fout ("Binary.bin", ios::binary);
const unsigned int RECORD_SIZE = 30; // was BUFFER_SIZE
char buffer[RECORD_SIZE] = {0}; // zero init buffer
while (fin.getline (buffer, RECORD_SIZE))
{
fout.write (buffer, RECORD_SIZE);
// refill buffer with zeroes for next time round
fill_n (buffer, RECORD_SIZE, 0);
}
fin.close ();
fout.close ();
}
void Binary_Search (const string& filename, string SearchVal)
{
ifstream file (filename.c_str(), ios::binary);
if (file.is_open())
{
cout << "The file is opened"<< endl;
cout << "\n";
}
else
{
cout << "Error opening file"<< endl;
cout << "\n";
return; // no point continuing Binary_Search() if file failed to open!
}
const unsigned int RECORD_SIZE = 30; // was BUFFER_SIZE
char buffer[RECORD_SIZE] = {0}; // zero init buffer
int recordCount = 0;
int recordWanted = -1;
while (file.read(buffer, RECORD_SIZE))
{
if(SearchVal == buffer)
{
recordWanted = recordCount;
// if this was just a naive search loop could bail out now...
}
cout << recordCount << " : " << buffer << "\n";
// refill buffer with zeroes for next time round
fill_n (buffer, RECORD_SIZE, 0);
++recordCount;
}
cout << "\n";
cout << "file contains " << recordCount << " records\n";
cout << "\n";
if (recordWanted == -1)
cout << "record wanted could not be found\n";
else
cout << "record wanted is at index " << recordWanted << " records\n";
cout << "\n";
}
int main()
{
Create_Bin_File();
string word;
cout << "Enter word, that you want to find in a file: " << endl;
cin >> word;
Binary_Search("Binary.bin", word);
return 0;
}
TASK: "Write a program in C ++. If the program works with a file, you should not copy the entire content of the file in operative memory. File component means fixed-length record. H7. Write a program that puts all standard C ++ reserved words in an ordered table (Ordered table as far as i understood means that these words are in alphabetic order). Write a function, which, using binary search, checks if an input string (length 30) is a C ++ reserved word or not. Table should be made as direct access file. C ++ reserved program should read from a text file."
grek40 solution on BinarySearch function:
So I make the record function:
std::string GetRecord(std::ifstream& inFile, int pos)
{
char buffer[RECORD_SIZE];
// clear possible flags like EOF, before moving the read position
inFile.clear();
// set the file read position to the requested record position
inFile.seekg(pos * RECORD_SIZE, std::ios::beg);
inFile.read(buffer, RECORD_SIZE);
// note: automatic conversion from char[] to std::string
return buffer;
}
And Binary Search funtion: (Solved - WORKING!)
void Binary_Search (const string& filename, string SearchVal)
{
ifstream file (filename.c_str(), ios::binary);
if (file.is_open())
{
cout << "The file is opened"<< endl;
cout << "\n";
}
else
{
cout << "Error opening file"<< endl;
cout << "\n";
return; // no point continuing Binary_Search() if file failed to open!
}
int pos = 0;
int lowerLimit = 0;
int recordCount = 73; // Calculated before[I'll change this part, when I get this function working]
// At this point, there's exactly 73 records in .bin file
char buffer[RECORD_SIZE] = {0}; // zero init buffer (while loop will overwrite with record values)
int upperLimit = recordCount;
while ( (lowerLimit < upperLimit) ) // Searching as long as it doesn't find it
{
pos = (lowerLimit + upperLimit) / 2;
std::string buffer = GetRecord(file, pos);
if (buffer == SearchVal)
{
cout << "Found!";
lowerLimit = 1; // For stopping (If found!)
upperLimit = 0; // For stopping
}
else if (SearchVal > buffer)
{
lowerLimit = pos + 1;
}
else if (SearchVal < buffer)
{
upperLimit = pos;
}
}
}
As far as I can see, you have a solution where you move all given words from the textfile to the binary file and you are able to find words in the binary file if they exist there.
I suppose you created your binary file with sorted records of equal length (30), where the text part of each record is zero-terminated.
Now, lets create a function that takes an opened binary file stream and a record position and returns the string at that record position:
std::string GetRecord(std::ifstream& inFile, int pos)
{
char buffer[RECORD_SIZE];
// clear possible flags like EOF, before moving the read position
inFile.clear();
// set the file read position to the requested record position
inFile.seekg(pos * RECORD_SIZE, std::ios::beg);
inFile.read(buffer, RECORD_SIZE);
// note: automatic conversion from char[] to std::string
return buffer;
}
For binary search, you should define an upper and lower limit for your search position. Note that the upper limit is lastItemPosition + 1, so you never actually access this position in zero based index.
int lowerLimit = 0;
int upperLimit = recordCount; // count when reading the lines in .txt
You need to search for a result as long as you didn't find it and lowerLimit < upperLimit.
Your next search word is at position = (lowerLimit + upperLimit) / 2;.
Compare the word to your search text. On equality, you are done.
If the word is less than the search text, your result position can be at higher indices than what you just looked at. So you need to adjust lowerLimit = position + 1
If the word is greater than the search text, your result position can be at lower indices than what you just looked at. upperLimit = position
You repeat the search with your adjusted upper and lower limits as described.