Binary Search an array of strings

Question

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

LearningC · Accepted Answer · 2014-03-20 19:22:51Z

1

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

edited Mar 20, 2014 at 19:22

answered Mar 20, 2014 at 18:58

LearningC

3,1621 gold badge15 silver badges19 bronze badges

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

6 Comments

attaboy182 Over a year ago

because you don't use relational operators for strings; and that's because when you do so you are comparing the address of where the strings are stored. And, that's an error.

user3443512 Over a year ago

I tested this out and it worked partially. So, now my program is crashing and also, some of the words that I'm testing are in my list are not showing up true in this search.

LearningC Over a year ago

@user3443512 this code looks fine. can you post the input and output for which program crashes. and make sure that input words are sorted.

user3443512 Over a year ago

@LearningC I figured out the crashing problem. For some reason when I used strcmp it was making the program crash. So, I changed it to strcasecmp and it works just fine now. However, my new problem is with my linear search! It doesn't stop, meaning the program keeps running after finding the words in the list. This is what my linear algorithm looks like:

user3443512 Over a year ago

int i = 0; for (i=0; i < MAX_NB_WORDS; i++){ if (strcasecmp(w,words[i])== 0){ return 1; } } return 0;

|

ajay · Accepted Answer · 2014-03-20 19:35:23Z

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

Collectives™ on Stack Overflow

Binary Search an array of strings

2 Answers 2

6 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related