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.

Answer 1

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