Binary Search Algorithm for a "text file" in C++

[iantac]

I'm creating a program that will search for a word in a text file using binary search algorithm. I already read about binary search. Anyway, assuming the text file that needs to be searched is "abc.txt" that contains:
ABC DEF Rudolf Andrew James Robert Ryan Six Seven Eight Ten Twenty Four

I run the program and entered the filename and it can only found some words like "Ryan" and "Rudolf". The program can't find other words that exist in the text file like Andrew. So I tried to add some codes so that I will see how the program finds the words (The line of codes with asterisk comments on it) and added a delay of 1sec. I need to find all the words that exist in the text file. Please help me

EDIT: I am using Microsoft Visual Studio 2010 PRO

#include<iostream>
#include<fstream>
#include<ctime>
#include<string>
#include<Windows.h>

using namespace std;

void main(void)
{
	fstream file;
	string f_skeyword,search,filename,g;
	float first=0.0,searchruntime=0.0;
	int middle=0,last=0;
	bool found=FALSE;
	clock_t search_start,search_end;
	
	cout<<"BINARY SEARCH ALGORITHM\n";
	cout<<"Enter filename (.txt): ";
	cin>>filename;
	cout<<"Enter word to be searched: ";
	cin>>f_skeyword;

	search_start=clock();
	file.open(filename);
	if(!file.is_open())
	{
		cout<<"Cannot find file\nProgram will now exit\n";
		system("pause");
		exit(1);
	}

	file.seekg(0,ios::beg);
	first=file.tellg();
	file.seekg(0,ios::end);
	last=file.tellg();
	file.seekg(0,ios::beg);
	while(first<=last)
	{
		middle=(first+last)/2;
		cout<<first<<" "<<last<<" "<<" "<<middle;  //**
		file.seekg(middle);
		file>>search;

		cout<<search<<endl;  //**
		if(search<f_skeyword)  
		{
			first=middle+1;
			cout<<"a";  //**
		}
		else if(search>f_skeyword)  
		{
			last=middle-1;
			cout<<"b";  //**
		}
		else
		{
			found=TRUE;
			break;
		}
		cout<<first<<" "<<last<<" "<<" "<<middle<<endl;  //**
		Sleep(1000);
	}
	if(found)
		cout<<f_skeyword<<" Found\n";
	else
		cout<<f_skeyword<<" Not found\n";
	search_end=clock();
	searchruntime=((float)search_end-(float)search_start);
	cout<<"Search Time: "<<searchruntime<<"ms (Milliseconds)"<<endl;
	system("pause");
}

[TheIdeasMan]

Are you sure first should be a float?

[iantac]

Oh sorry I forgot to change it to int. Anyway, still same result It can't find the existing words in the file

float searchruntime=0.0;
int first=0,middle=0,last=0;

[TheIdeasMan]

Maybe try using the debugger?

[iantac]

I don't know how to use the debugger.. I just need a 'more direct' answer. Will I replace a certain code?? etc...

I already searched other codes for binary search but most examples that I can find are binary search algorithm for arrays not for text files

[TheIdeasMan]

Ok just put more cout's in the code, maybe this one in all the if clauses.

cout<<first<<" "<<last<<" "<<" "<<middle; //**

A poor answer I know - might still help though.

[MrHutch]

I'm pretty sure binary searches will only work on sorted lists. The words in your text file would need to be sorted first. You'd probably get screwy results otherwise.

As for other examples using arrays, why not just read the lines from your text file into an array (or, better yet, a vector).

[iantac]

how will I 'sort' the word of the text file?
Anyway that abc.txt is just a sample that's why it only contains 13 words.
I will use the program to search a word in a text file with 100, 1000, 10000, 100000, and 1000000 records and each record contains 256 characters. :)))

I already finished coding a linear search algorithm and I am creating another search algorithm (the binary search algorithm which I'm doing right now)

[viliml]

how will I 'sort' the word of the text file?

Umm, std::sort()?

[MrHutch]

Yep, what viliml said.

Or implement your own sort algorithm. A bubble sort is pretty easy to do, providing you have a lax deadline and endless amounts of patience.

Doesn't matter if the file is 10 or 100,000 lines long; as long as it's sorted the binary search will work (albeit at a different speeds).

[viliml]

Yes, bubble sort with 1000000 records of 256 chars... Ouch... It has a complexity of 256000000² operations...

[viliml]

It would take 2 years, assuming a billion instructions per second.

[MrHutch]

Christ, of course. Good point. I didn't think about the number of files when sorting. :-)

Amended original suggestion.

[viliml]

With a N log N sorting algorithm it would take... around 7 sec! plus 27 nanoseconds of binary search, it's OK.

[iantac]

haha I did it THANKS A LOT!

first I placed all the words in a array and I created a quicksort algorithm and used the binary search.. HAHA :))

It searched the word in the file faster than the linear search that I've created.