//
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;
}
}

```