Thread: Help with Binary Search

i need help finishing the tail end of this program, i'm not sure how to finish the Binary Search at the end of the program, can someone help please!!

Code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream.h>
#include <fstream.h>
#include <ctype.h>
#include <iomanip.h>


class wordanddef
{
public:
	char* word;
    char* def;

};


int loaddata(char *fn, wordanddef wadptr[]);
void sortdata(int numlines, wordanddef wadptr[]);
int findword(int numlines, wordanddef pwordanddef, char *wrd)

int main(void)
{
char fname[100], sword[20], origword[20];
int linecnt, fwordnum, ccnt;
wordanddef pwordanddef[400];

	strcpy(fname, "defs.dat");

	linecnt=loaddata(fname, pwordanddef);
	if(linecnt==-1)
	{
	cout<<"File could not be opened";
        system("Pause");
		exit(1);
	}

    sortdata(linecnt, pwordanddef);

	while(strcmp (sword, "")!=0)
	{
		cout<<"\nEnter the word to search for, or hit enter to exit:  ";
		cin.getline(sword, 20);
		strcpy(origword, sword);

		fwordnum=findword(linecnt, pwordanddef, sword);

		if(fwordnum==-1)
            cout<<"\nNot found.\n";
		else
		{
			cout<<"\nWord found.\n";
			cout<<"Original Word As Typed: "<<origword<<"\n";
			cout<<"Word: "<<pwordanddef[fwordnum].word<<"\n";
			cout<<"Definition: "<<pwordanddef[fwordnum].def<<"\n";

		}
	}

}

int loaddata(char *fn, wordanddef wadptr[])
{
ifstream file;
char line[80];
int cnt=0;

char tmpWord[50];
char tmpDef[500];


	file.open(fn);

	if(file.fail())
        return -1;

     while (file.peek() != EOF)
     {
       file >> tmpWord;
       file >> ws;
       file.getline(tmpDef, 999);

       wadptr[cnt].word = new char[1+strlen(tmpWord)];
       strcpy(wadptr[cnt].word, tmpWord);

       wadptr[cnt].def = new char[1+strlen(tmpDef)];
       strcpy(wadptr[cnt].def, tmpDef);
       cnt++;
       }
	file.close();

	return cnt;
}

void sortdata(int numlines, wordanddef wadptr[])
{
int swap, sortcnt;
wordanddef twadptr;

	swap=1;
	while(swap)
	{
		swap=0;
        sortcnt=0;
		while(sortcnt<numlines-1)
		{
			if(strcmp(wadptr[sortcnt].word, wadptr[sortcnt+1].word)>0)
			{
				twadptr=wadptr[sortcnt];
				wadptr[sortcnt]=wadptr[sortcnt+1];
				wadptr[sortcnt+1]=twadptr;
				swap=1;
			}
			sortcnt++;
		}
	}
}

int findword(int numlines, wordanddef pwordanddef, char *wrd)
{
int bottom = 0;
int top = numlines - 1;
int middle;

while (bottom < top)
{
 middle = (top + bottom)/2;
 if (wrd < pwordanddef[middle])
   top = middle +1;
 else
     bottom = middle;
}
 if (wrd == pwordanddef[bottom])

This is 100% personal preference but I prefer

Code:

middle =(top - bottom)/2 + bottom;

over

Code:

middle =(top + bottom)/2;

Reasoning: it is possible for an array to be of such a large size that the value of top + bottom to overflow INT_MAX (think if the item you were looking for was the second to last item in the arry).
Using top - bottom elimates that possiblity.