CODEWITHSUNDEEP
c
user3443512
user3443512

Reputation: 1

Binary Search an array of strings

I need help with binary searching arrays, my problem is that I feel like I have all the right requirements but it's not searching at all. I don't get any error messages. Just not getting the results I want. The array is globally initialized as well as the max number of words. This is what my function looks like:

int wordsFindFast(const char const* w){
/*
    ROLE            Determines whether a given word is in our words array
                    Implements fast binary search algorithm
    PARAMETERS      w   word to look for in the words array
    RETURN VALUE    1   true if the word was found
                    0   false if the word was not found
*/

int first, middle, last;

first = 0;
last = (MAX_NB_WORDS) - 1;
middle = (first+last)/2;

while(first <= last)
{
    if (words[middle] < w){
        first = middle + 1;
    }//end if
    else if(words[middle] == w){
        return 1;
    }//end else if
    else
        last = middle - 1;
        middle = (first + last)/2;
}//end while

return 0;
}

Upvotes: 0

Views: 1744

Answers (2)

ajay
ajay

Reputation: 9680

You cannot compare string in C. You should compare them character-by-character using the standard library function strcmp declared in the header string.h. Also, note that

const char const *w

in the parameter list of the function wordsFindFast is the same as

const char *w

which means w is a pointer to an object of type char which is constant, i.e., is read only. You should change your function to - 

int wordsFindFast(const char *w) {
    int first = 0;  
    int last = MAX_NB_WORDS;
    int middle;

    int cmpval;

    while(first <= last) {
        middle = (first + last) / 2
        cmpval = strcmp(w, words[middle]);
        if(cmpval == 0)
            return 1;
        else if(cmpval < 0)
            last = middle - 1;
        else
            first = middle + 1;
    }
    return 0;
}

Upvotes: 0

LearningC
LearningC

Reputation: 3162

you can not compare strings in c as

if (words[middle] < w)

use strcmp() as,

while(first <= last)
{
    if (strcmp(words[middle],w)==0)
    {
         return 1;

    }
   else if(strcmp(words[middle], w)<0)
    {
        first=middle+1;
    } 
    else
        last = middle - 1;
  middle = (first + last)/2;
}//end while

Upvotes: 1

Related Questions