Binary search of string array in C

Question

I want to write a binary search for a string array in C.

I have written this code and it compiles with no errors but when i try to search it gives no results. Any help would be appreciated.

String is a type def. Sorry for not clarifying this in the beginning.

//Looks up word s, in dictionary.
bool lookup(string s)
{  
    int min = 0;
    int max = dictionary.size - 1;
    int mid;
    bool found = false;

    while (min <= max && !found)
    {
        mid = (min + max) /2;
        if (dictionary.words[mid].letters == s)
            found = true;
        else if (dictionary.words[mid].letters > s)
            max = mid -1;
        else
            min = mid + 1;
    }
    return found;
}

How is this C? Is string a typedeff'ed struct, or is this C++? — William Pursell
– William Pursell, Commented Jan 7, 2013 at 12:20
Are you using C or C++? You can't use std::string in C, and if you're using cstrings (arrays of char), you can't use == to compare them (or, at least not the way you think). — sonicwave
– sonicwave, Commented Jan 7, 2013 at 12:20
The algorithm looks correct.Point us to the code if you need help. — Flash
– Flash, Commented Jan 7, 2013 at 12:20
Step through it with a debugger when you know what result you are expecting, and see how and when the behaviour differs from what you expected. — Vicky
– Vicky, Commented Jan 7, 2013 at 12:38

StoryTeller - Unslander Monica · Accepted Answer · 2013-01-07 12:21:22Z

1

String in C are just char arrays, and since comparison between arrays using == only compares the start address, you need to use the librray function strcmp in string.h to compare the contents of the arrays. Like so:

if (strcmp(dictionary.words[mid].letters, s) == 0)

EDIT

I see that despite the c tag, you have some sort of string type. Is this C or C++?

answered Jan 7, 2013 at 12:21

StoryTeller - Unslander Monica

172k22 gold badges401 silver badges481 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Techmonk · Accepted Answer · 2013-01-07 13:05:12Z

I think it would help if you pasted the string and the dictionary structures.

Assuming that the Dictionary is a sorted array of words.Strings (array of char) and string is a array of char as well then I would assume that when you do dictionary.words[int].letters the return type is a memory and same is the case with s. As the two strings are saved at different memory locations you are unable to find the string.

Try iterating through the string to compare the strings

bool lookup(string s)
{  
    int min = 0;
    int max = dictionary.size - 1;
    int mid;
    bool found = false;
    int i;
    int length = 0;                 //calculate the length of the input string
    while (s[length] != '\0')
    {
    length++;
    }

    while (min <= max && !found)
    {
        mid = (min + max) /2;
        for(i=0;i<length;i++)
        {
            if(dictionary.words[mid].letters[i] == '\0')
                break;
            if (dictionary.words[mid].letters[i] == s[i])
                continue;
            else if (dictionary.words[mid].letters[i] > s[i])
                max = mid -1;
            else
                min = mid + 1;
            break;
        }
        if(i==length)
            found=true;
    }
    return found;
}

I have not compiled the code but this should give you the gist.

Collectives™ on Stack Overflow

Binary search of string array in C

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related