binary search

[rivkyfried1]

I am trying to write a function which performs a binary search. A two dimensional character array will be sent to the function as a first parameter. The second parameter is an integer and gives the function information as to how many pieces of data are in the array in parameter 1. The third parameter is a string from a two dimensional array which needs to be compared to the strings in the array which is the first parameter. The fourth parameter is an integer, which tells the program about the position in the array of the string in the third parameter. Here is an excerpt from my code. The function is not working. Please shed light on why this might be the case. THANKS!

#include <stdio.h>
#include <string.h>
#include <ctype.h>
int binarysearch (char [], int, char [], int);
main ()
{
char cum_nouns [700] [21];
int file_len=0;
char noun [6] [21];
int count;

location=binarysearch(cum_nouns [i] , file_len, noun[count], count);

}
int binarysearch (char data [], int n, char newitem [], int datapositionofnewitem)
    {
        int low, high, test, findnewitem;
        low=0;
        high=n-1;
        while (low<=high){
            test=(low +high/2);
            findnewitem=strcmp (newitem[datapositionofnewitem], data[test]);
            if(findnewitem==0)
            return test;
            else if (findnewitem<0)
            high = test -1;
            else
            low=test+1;
        }
        return -1;
    }

[jimblumberg]

main.c|6|warning: return type defaults to ‘int’|
main.c||In function ‘main’:|
main.c|12|error: ‘location’ undeclared (first use in this function)|
main.c|12|error: (Each undeclared identifier is reported only once|
main.c|12|error: for each function it appears in.)|
main.c|12|error: ‘i’ undeclared (first use in this function)|
main.c||In function ‘binarysearch’:|
main.c|22|warning: passing argument 1 of ‘strcmp’ makes pointer from integer without a cast|
/usr/include/string.h|142|note: expected ‘const char *’ but argument is of type ‘char’|
main.c|22|warning: passing argument 2 of ‘strcmp’ makes pointer from integer without a cast|
/usr/include/string.h|142|note: expected ‘const char *’ but argument is of type ‘char’|
||=== Build finished: 4 errors, 3 warnings ===|

If you read your error messages and try to fix them your program will have a better chance of doing what you expect.

Do you understand what the error messages are telling you?

If not please ask.

In future posts please post the entire error/warning messages you received when you compiled your code. The error messages have important information to help solve problems.

Jim

[rivkyfried1]

I didn't get any of these error messages. The reason you got them when the program ran, is because the code that i sent was an excerpt from my program. My program is 1000s of lines long. I couldn't send the whole thing. I did not get error messages when I ran my program. The program crashed when it got up the part with the function. I'll now send a new excerpt which is more complete. Please note: I know for sure that the problem with my program is in the function. The program runs well without the function. If you get error messages at this point, it's because i didn't excerpt enough from it. Please pay special attention to the protocall, the call to the function and the complete function after the main program. MANY THANKS!

#include <stdio.h>
#include <string.h>
#include <ctype.h>
int binarysearch (char [], int, char [], int);
main ()
{
char cum_nouns [700] [21];
int file_len=0;
char noun [6] [21];
int count;
int location;
char yes_or_no [12];
 int yes;
 int no;
int length;
    char username [6];
    char filename [256];
    char filename1 [256];
    char filename2 [256];
    char filename3 [500];
    char filename4 [256];
    char filename5 [256];
    char file6suffixes [256];
    char file7possessivepronouns [256];
    char file_twowordverbs[256];
    char file_secondpartoftwv [256];
    char filetwowordverbspt [256];
int temp;
int file_len;
FILE * outfile;
FILE * outfilef;
FILE * infile;
FILE * infilev;
printf ("Hi, Please type in your user name in lowercase letters only.\n");
    scanf ("%s", username);
    length = strlen (username);
    strncpy (filename, username, length);

printf ("Hi. Using this program, you'll enter all of the new words you taught your \nstudents today.\n\n");
    printf ("We'll start with nouns. Did you learn any new nouns today?\n\n");
    printf ("Type yes or no. Use lowercase only.\n");
    scanf ("%s", & yes_or_no) ;
    yes = strcmp ("yes", yes_or_no);
    no = strcmp ("no", yes_or_no);
    if ((yes !=0) && (no !=0)) {
    printf ("\n\nERROR. Please enter yes or no in lowercase.\n");
    scanf ("%s", & yes_or_no);
    yes = strcmp ("yes", yes_or_no);
    no = strcmp ("no", yes_or_no);
           }
    strncpy (filename, username, length);
    strcat (filename, "nouns.txt");
    outfile = fopen (filename, "a");
    for (count = 0; no !=0; count = count + 1) {
    temp = count + 1 ;
    printf ("\nplease enter noun %d\n", temp);
    scanf ("%s", & noun [count]);
    fprintf (outfile, "%s ",  noun [count]);
    printf ("\n\nDo you want to enter another noun?");
    printf (" Enter yes or no.\n Use lowercase only.\n");
    scanf ("%s", & yes_or_no);
    yes = strcmp ("yes", yes_or_no);
    no = strcmp ("no", yes_or_no);
        if ((yes !=0) && (no !=0)) {
            printf ("\nERROR. Please enter yes or no in lowercase only.\n");
            scanf ("%s", & yes_or_no);
            yes = strcmp ("yes", yes_or_no);
    no = strcmp ("no", yes_or_no);


                                       }
    }
    fclose (outfile);

strncpy (filename4, username, length);
strcat (filename4, "worksheet.txt");

infile = fopen (filename, "r");
outfile = fopen (filename4, "a");
for (i = 1; i < file_len +1; i ++){
   fscanf (infile, "%s", & cum_nouns [i]);
        fprintf (outfile, "%s\n\n\n", cum_nouns[i]);

}

fclose (infile);
fclose (outfile);

location=binarysearch(cum_nouns [i] , file_len, noun[count], count);

}
int binarysearch (char data [], int n, char newitem [], int datapositionofnewitem)
    {
        int low, high, test, findnewitem;
        low=0;
        high=n-1;
        while (low<=high){
            test=(low +high/2);
            findnewitem=strcmp (newitem[datapositionofnewitem], data[test]);
            if(findnewitem==0)
            return test;
            else if (findnewitem<0)
            high = test -1;
            else
            low=test+1;
        }
        return -1;
    }

[laserlight]

rivkyfried1, post the smallest and simplest compilable program that demonstrates the run time error.

[rivkyfried1]

the function is the part that the program crashes on:

In the following lines, I will include the protocall before the main program, the call to the function, and the function itself after the main program.

protocall:
int binarysearch (char [], int, char [], int);


call to function:
location=binarysearch(cum_nouns , file_len, noun, count);


function itself:
int binarysearch (char data [], int n, char newitem [], int datapositionofnewitem)
    {
        int low, high, test, findnewitem;
        low=0;
        high=n-1;
        while (low<=high){
            test=(low +high/2);
            findnewitem=strcmp (newitem[datapositionofnewitem], data[test]);
            if(findnewitem==0)
            return test;
            else if (findnewitem<0)
            high = test -1;
            else
            low=test+1;
        }
        return -1;
    }

Please let me know if this is enough info. If it is not, I will send more of the code. THANKS so much! I am pretty stuck on this.

[laserlight]

Well, by inspection your implementation looks correct, or at least it should not be causing the program to crash. I could be wrong, of course, but that is what I see.

If you actually want me to run the program and confirm what you see, you should do what I told you to do in post #4.

[anduril462]

You're not doing what you described in your first post:

A two dimensional character array will be sent to the function as a first parameter.

You're sending a 1-d char array. I think you mean "char *data[]"

The third parameter is a string from a two dimensional array which needs to be compared to the strings in the array which is the first parameter.

Here, you describe a 1-d array, which you are passing, but you treat it as a 2-d array in your strcmp call: newitem[datapositionofnewitem]. This is bad for strcmp.

These are likely causing your program to crash on the strcmp, since you're passing in 2 characters (0-255, invalid memory addresses) instead of pointers to the start of the strings.

However, since you are searching for newitem[datapostionofnewitem], and don't use any other elements from the newitem array, I would simply pass in newitem[datapostionofnewitem] and drop the 4th parameter, so you function looks like this:

int binarysearch(char *data[], int n, char *newitem)
{
    ...
    findnewitem = strcmp(data[test], newitem);
    ...
}

These types of problems should have caused some compiler warnings/errors somewhere. Turn all error reporting on and accept nothing less than error free code. This should help avoid such problems.

[nonoob]

This part jumps out at me:

test=(low +high/2);

I bet it should be (low + high) / 2

[rivkyfried1]

Thanks for your suggestion. I tried to modify the code so that the function looks like this:

Protocall: 

int binarysearch(char *[], int, char *);


call to function: 
location=binarysearch(cum_nouns, file_len, noun[count]);


function itself:
int binarysearch(char *data[], int n, char *newitem)


    {
        int low, high, test, findnewitem;
        low=0;
        high=n-1;
        while (low<=high){
            test=(low +high)/2;
            findnewitem = strcmp(data[test], newitem);
            if(findnewitem==0)
            return test;
            else if (findnewitem<0)
            high = test -1;
            else
            low=test+1;
        }
        return -1;
    }

anduril462 - is this what you meant? my program is still crashing when it gets to the function.

[anduril462]

anduril462 - is this what you meant? my program is still crashing when it gets to the function.

Yes, that was what I meant. Unfortunately, I can't run this through a compiler right now to test it, but that should have solved the problem within your binarysearch function. You could still have a problem if you don't pass in parameters the correct way. Try whipping up a small sample program with just that function in it, an array of 5 strings or so, and a sample string to search for, and nothing else. If you still have trouble, come back with what you have and I will give it another go when I get home tomorrow morning.

Another thing, which shouldn't cause your program to crash, but may still prove a logical error is the order of your arguments to strcmp in binarysearch. strcmp returns a negative value when the first argument is less than the second, and a positive when the first argument is greater than the second. That means, if your "test" item is smaller than the item you're searching for, your program (as it stands) will move the high value down, making it impossible to find your search string. Switch the order of arguments to strcmp, and you should be better off. Perhaps this is what Adak was getting at in his comment.

[rivkyfried1]

Thanks for your help. Thankfully, it now works. Here is what I did:

Protocall:
int binarysearch(char data[][21], int n, char *newitem[][21], int positionofnewitem);

Call to function:
location=binarysearch(cum_nouns, file_len, noun, count);

function:
int binarysearch(char data[][21], int n, char *newitem[][21], int positionofnewitem)



    {
        int low, high, test, findnewitem;
        low=0;
        high=n-1;

        while (low<=high){
          test=(low +high)/2;
            printf ("\n\nthe value of test is %d", test);
            printf ("\nthe data of test is %s", data[test]);
            findnewitem=strcmp (newitem[positionofnewitem], data[test]);
            printf ("\n\nI am comparing %s %s.\n\n",newitem[positionofnewitem], data[test] );
            printf ("\n\nthe findnewitem is equal to %d\n", findnewitem);
            if(findnewitem==0)
            return test;
            else if (findnewitem<0)
            high = test -1;
            else
            low = test+1;
        }
        return -1;
    }

I think that my code is correct with regard to how the high and low values are manipulated. If the new item is smaller than the item in the array to which it is comparing it to, it will lower the high value. This is exactly what we want, the upper limit to be made lower so that the loop will search only through items lower than the the item in the array that the program was up to.. The program is doing a search on a sorted array.. so this makes sense. i believe that the logic in my code is correct.

[anduril462]

Your code in post #12 is logically sound, but I was looking at your code from post #9, which had newitem and data switched in the strcmp, which would not have worked. And I just read my post #7 and realized for some reason that I switched the parameter order there, probably causing headaches all around. Sorry about that!

[rivkyfried1]

No problem! Thanks for your help!