//
you're reading...
Uncategorized

C++ Spell Checker using Binary Search Algorithm: Procedural and Recursive

Here are two C++ programs illustrating binary search algorithm. The first is procedural implementation using a while loop, and the second is recursive.

#include <iostream>
#include <string>
#include <fstream>
using namespace std;

int main() {
    const int SIZE = 235886;
    ifstream file("/usr/share/dict/words");
    if(file.is_open()) {
        string myArray[SIZE];

        for(int i = 0; i < SIZE; ++i) {
            file >> myArray[i];
            myArray[i][0]= tolower(myArray[i][0]);
        }

       cout << "Enter a search term:" ;
       string key;
       cin >> key;
       cout << "You entered the search term: " << key << endl;

       int lowerbound = -1;
       int upperbound = SIZE;
       int position = (lowerbound + upperbound) / 2;
       int count = 1;

       while((myArray[position] != key) && (lowerbound <= upperbound)) {
              cout << count << ":->  " << myArray[position] << " at position " << position <<  endl;
              if (myArray[position] > key) 
                    upperbound = position - 1;                             
              else                                 
                   lowerbound = position + 1;     
              position = (lowerbound + upperbound) / 2;
              count++;
       } // end of while

      if (lowerbound <= upperbound)
            cout<< "The string " << key << " was found in array at position "<< position<<endl<<endl; 
      else
            cout<< "Sorry, the string " << key << " is not in this dictionary." << endl;  
}
}




#include <iostream>
#include <string>
#include <fstream>
using namespace std;



bool BinarySearch(string  A[], int first, int last, string  key) {

   if (first <  last-1) {
       int mid = (first + last) / 2;  
       if (key == A[mid]) 
           return true;  
       else if (key < A[mid]) 
           return BinarySearch(A, first, mid, key);
       else
           return BinarySearch(A, mid, last, key);
   }
   else return false;    // failed to find key
}

 
int main() {
    const int SIZE = 235886;
    ifstream file("/usr/share/dict/words");
    if(file.is_open()) {
        string myArray[SIZE];
 
        for(int i = 0; i < SIZE; ++i) {
            file >> myArray[i];
            myArray[i][0]= tolower(myArray[i][0]);
        }
 
       cout << "Enter a search term:" ;
       string key;
       cin >> key;
       cout << "You entered the search term: " << key << endl;
       bool keyfound = BinarySearch(myArray, -1, SIZE, key);
       if (keyfound)
            cout<< "The string " << key << " was FOUND." << endl; 
       else
            cout<< "Sorry, the string " << key << " is NOT in this dictionary." << endl;  
    }
}

Advertisements

Discussion

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: