Imagine you're holding a massive, 1,000-page physical dictionary. If I asked you to tell me if the word "syzygy" is in there, you wouldn't start on page one and read every single word until you hit the 'S' section. That would take hours. Instead, you'd open the book roughly in the middle, see that you've landed on the 'M's, realize 'S' comes after 'M', and completely ignore the first half of the book. You keep splitting the remaining pages in half until you've narrowed it down to a handful of words.

This is exactly how we're going to build our spell checker. In C, we aren't dealing with paper, but the logic is identical. Our "dictionary" will be a sorted text file, and our "flipping to the middle" will be a binary search algorithm. Here is how the analogy maps to the code: the sorted text file is our book, the strcmp() function is our eye reading a word on a page, and the binary search logic is the process of halving the search area.

Loading the Lexicon into Memory

Reading from a disk is slow. If we want our spell checker to feel snappy, we shouldn't search the file on the hard drive; we should load the words into an array of strings (a pointer to pointers) in RAM. I usually recommend loading the dictionary once at startup so the actual checking happens at lightning speed.

char **dictionary;
int word_count = 0;

void load_dictionary(const char *filename) {
    FILE *file = fopen(filename, "r");
    if (!file) {
        perror("Could not open dictionary");
        exit(EXIT_FAILURE);
    }

    char buffer[100];
    // First pass: count the words to allocate the right amount of memory
    while (fgets(buffer, sizeof(buffer), file)) {
        word_count++;
    }

    // Allocate memory for the array of string pointers
    dictionary = malloc(word_count * sizeof(char *));

    rewind(file);
    int i = 0;
    while (fgets(buffer, sizeof(buffer), file)) {
        // Remove newline characters and duplicate the string into our array
        buffer[strcspn(buffer, "\n")] = 0;
        dictionary[i++] = strdup(buffer);
    }
    fclose(file);
}

The Binary Search Shortcut

Now that we have our words in a sorted array, we can avoid the "linear scan" (checking every word) which would be a nightmare for a dictionary of 100,000 words. Instead, we implement the binary search. I've found that the most common mistake here is getting the low and high indices slightly off, leading to an infinite loop. Watch those boundaries closely.

int is_valid_word(const char *word) {
    int low = 0;
    int high = word_count - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        int res = strcmp(word, dictionary[mid]);

        if (res == 0) {
            return 1; // Found it!
        }
        if (res > 0) {
            low = mid + 1; // Word is alphabetically "after" the middle
        } else {
            high = mid - 1; // Word is alphabetically "before" the middle
        }
    }
    return 0; // Not in the dictionary
}

Connecting the Logic to the User

At this point, we have a system that can take a single string and tell us if it's valid. To make this a real "spell checker," you'll need to wrap this in a loop that takes a sentence, splits it into individual words (using something like strtok), and flags the ones that return 0 from our is_valid_word function.

One thing to keep in mind: this basic version is case-sensitive. In a production environment, I'd suggest converting every word to lowercase before comparing it, otherwise "Apple" might be marked as misspelled just because the dictionary only contains "apple".

📋 Practical Task

The Case-Insensitive Typo Detector

Expand the spell checker logic provided in the lesson. Modify the is_valid_word function and the word-loading process so that the spell checker ignores capitalization. For example, if the dictionary contains "programming", the words "Programming", "PROGRAMMING", and "pRoGrAmMiNg" should all be flagged as correct.

• Implement a helper function to_lowercase(char *s) to normalize strings.
• Ensure that both the dictionary words (during load) and the user's input words are normalized before strcmp is called.
• Test your program with a small custom text file containing at least 10 sorted words.