Help with Binary Search

This is a discussion on Help with Binary Search within the C++ Programming forums, part of the General Programming Boards category; i need help finishing the tail end of this program, i'm not sure how to finish the Binary Search at ...

  1. #1
    Shake Zula- The Mic Rula!
    Join Date
    Sep 2004
    Posts
    69

    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])

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,699
    well, for an array of ints it'd be:

    Code:
    int bsearch(int value, int array[], int count) {
     int bottom = 0, 
         top = count-1,
         middle; 
     while (bottom <= top) {
      middle =(top + bottom)/2; 
      if(value == array[middle]) {
       return middle;
       } else if (value < array[middle]) {
       top = middle - 1;
       } else {
       bottom = middle + 1;
       }
      }
     return -1;
     }
    >> if (wrd < pwordanddef[middle])

    why are you comparing a char* to a struct?
    Code:
    bool fun(bool value)
    {
        return std::pow(std::exp(1), std::complex<float>(0, 1) 
        * std::complex<float>(std::atan(1)*(1 << (value + 2))))
        .real() > 0;
    }

  3. #3
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 04:15 PM
  2. deleting all nodes of a binary search tree...
    By sachitha in forum C++ Programming
    Replies: 3
    Last Post: 09-29-2004, 06:19 AM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21