0

So I've got the binary search function working for this problem, but I have no idea how to deal with the "found" flag portion of the problem. I think the idea is to add a "true" condition to the bool portion of the typedef struct "words", which is in the struct "dictionary". Just needing a nudge in the right direction. My attempt below is not working.

// Looks up word, s, in dictionary.  If found (for the first time), flags word as found (so that user can't score with it again) and returns true

bool lookup(string s) { // TODO int start = 0; int end = dictionary.size;

while (start <= end)
{
    int mid = (start + end) / 2;

    if (strcmp(s, dictionary.words[mid].letters) == 0)
    {
        dictionary.words[mid].found = true;
        return true;
    }
    if (strcmp(s, dictionary.words[mid].letters) < 0)
    {
        end = mid - 1;
    }
    if (strcmp(s, dictionary.words[mid].letters) > 0)
    {
        start = mid + 1;
    }
}
return false;

}

1

A few things. Valid indexes would probably range from 0 to size-1, and as you chose your interval boundaries as both being part of the interval, your initial interval end should include the -1, to avoid accessing a word after the list, where it can't be.

Do not call strcmp up to three times, but only once, remembering the result in some variable, and check the variable up to three times.

I would check for the flag already being present when you find the words being equal, and if it is already set, return false instead of setting the flag and returning true.

| improve this answer | |

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .