Applying binary search in a text file in c for line by line text

Question

I am trying to search a word in text file and I got kinda successful but the code doesn't always work. Its just that I don't understand why it doesn't work inside a loop but works when I do it manually.

I know its a lot to look at but please could anyone help me.

#include <stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>

void main()
{
    FILE *fp;
    fp=fopen("testdictionary.txt","r");

    char word[]="her";
    char line[7];
    int n;
    int upper_limit=48;
    int lower_limit=0;
    int result=-1;

    while(result!=0) {
        n=(upper_limit+lower_limit)/2;
        printf("Value of n:%d ",n);
        fseek(fp,n,SEEK_SET);

        // setting the file pointer to the beginning of the word. --
        fseek(fp,-1,SEEK_CUR);
        char tst;
        do {
            fseek(fp,-1,SEEK_CUR);
            if(ftell(fp)==0) {
                break;
            }

            tst=fgetc(fp);
            if(tst=='\n') {
                break;
            }

            fseek(fp,-1,SEEK_CUR);
        } while(tst!='\n');
        //----------------------------------------------------------

        fgets(line,7,fp);
        result=strcmp(line,strcat(word,"\n"));
        printf(" Result:%d ",result);

        if(result==1) {
            upper_limit=n;
            printf("Required 'word' is above the line of text.\n");
        }
        else if(result==-1) {
            lower_limit=n;
            printf("Required 'word' is below the line of text.\n");
        }
        else if(result==0) {
            printf("Word found");
        }
    }
}

My text file

aoo
bpp
cas
dzx
edf
fvb
gty
her
iwe
jqw

Output (When I run the above code.)

Value of n:24  Result:-1 Required 'word' is below the line of text.
Value of n:36  Result:-1 Required 'word' is below the line of text.
Value of n:1322  Result:1 Required 'word' is above the line of text.
Value of n:329639  Result:1 Required 'word' is above the line of text.
Value of n:84052197

The part which I don't understand is that if I manually enter n=36, the result says 0 and word is found .But when I try searching automatically, even when the value of n becomes 36 after the 2nd step, the loop doesn't break and gives weird and large values of n.

So when I put n=36(shown below) myself, I get the expected output that the word "her" is found.

while(result!=0)
{
    // n=(upper_limit+lower_limit)/2;
    n=36;
    printf("Value of n:%d ",n);
    fseek(fp,n,SEEK_SET);

Output

Value of n:36  Result:0 Word found
Process returned 10 (0xA)   execution time : 0.141 s
Press any key to continue.

I don't know if this is how you are supposed to do binary search but this is what i know. I am just a beginner in programming.

Please add your input and output to the question as code blocks instead of showing screenshots. Show also how the expected output should look like. What do you mean with "if i manually enter n=36" Where do you enter this? — Bodo
– Bodo, Commented Mar 1, 2019 at 16:21
@SandeshGhimire you should also make an effort and indent your code properly. Readable code is most important for finding bugs. — Jabberwocky
– Jabberwocky, Commented Mar 1, 2019 at 16:43

Weather Vane · Accepted Answer · 2019-03-01 17:17:24Z

3

The function strcmp does not return specifically -1 or 1 (although it may do). It returns a value of 0, < 0 or > 0.

Also in

result = strcmp(line, strcat(word, "\n"));

you cannot concatenate anything to

char word[] ="her";

because the array has no room. It is better to remove the newline from the file string, than add it to your target string.

Even if you could, you are adding another newline in every iteration. So I suggest

fgets(line, 7, fp);
line [ strcspn(line, "\r\n") ] = '\0';      // truncate any newline
result = strcmp(line, word);
if(result > 0) {
    upper_limit = n;
    printf("Required 'word' is above the line of text.\n");
}
else if(result < 0) {
    lower_limit = n;
    printf("Required 'word' is below the line of text.\n");
}
else {   // no other possibility
    printf("Word found");
}

edited Mar 1, 2019 at 17:17

answered Mar 1, 2019 at 17:05

Weather Vane

34.8k7 gold badges43 silver badges63 bronze badges

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

2 Comments

Bodo Over a year ago

This buffer overflow when appending \n to word probably overwrites variable n. When I change the code to use char word[]="her\n"; and result=strcmp(line,word); it seems to work as expected.

Sandesh Ghimire Over a year ago

Now the program runs as expected. I changed the things you guys suggested. Thanks for the help.

Collectives™ on Stack Overflow

Applying binary search in a text file in c for line by line text

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related