a mistake in the c programming language book.wtf?

[KidMan]

in page 54 the binary search is all messed up
1-high=mid+1 ----> high=mid-1
2-the final return is the one which will return the value for the main fn because anyway the program will excute it no matter the target was found or not

I edited the code and this one works...

int binsearch(int x, int v[], int n)
{
int low, high, mid,found;
found=-1;
low = 0;
high = n - 1;
while (low <= high && found==-1) {
mid = (low+high)/2;
if (x < v[mid])
high=mid-1;
else if (x > v[mid])
low = mid + 1;
else /* found match */
found=mid;}
return (found); /* no match */
}

Plz guys if anyone spotted or spots any mistakes in the any book post to avoid learning wrong stuff and i'd appreciate it if the mod makes a sticky thread about it.

[caduardo21]

What version of the book are you refering to? I opened my The C Programming Language 2nd Edition book on page 54 and there's no binary search implementation on that page...

[KidMan]

i have the ebook and its the second edition........anyway its in chapter 2 the if else part

[Slacker]

>i have the ebook and its the second edition
K&R isn't available electronically. You're reading a pirated copy that's probably filled with typos and errors, unlike the actual printed book.

Cheers!

[kungtotte]

In The C Programming Language, 2nd Edition, the code-snippet you refer to can be found in Chapter 3, page 58.

Here is the original code-snippet from the book, in it's entirety:

/* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */
int binsearch(int x, int v[], int n)
{
    int low, high, mid;
    
    low = 0;
    high = n - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (x < v[mid])
            high = mid - 1;
        else if (x > v[mid])
            low = mid + 1;
        else /* found match */
            return mid;
    }
    return -1; /* no match */
}

I'm not an expert, but looking at your code and the original code I can't see why the original would be wrong.

Where is the error?

[KidMan]

the error(as i think) is that the function is anyway goinf to excute the return -1 statement whatsoever........what if it found the target?it will return middle?ok then its going to return -1

[kungtotte]

Huh? If the target is found, then the index of the target is returned. If the target is not found, -1 is returned.

[dwks]

what if it found the target?it will return middle?ok then its going to return -1

A function only executes one return statement, at which point the function returns to whatever function called it.

[Salem]

For those who have a pukka printed copy of K&R-II (and who wouldn't have), then this is perhaps relevant.
http://cm.bell-labs.com/cm/cs/cbook/2ediffs.html

[KidMan]

thanks guys seems i didnt understand the return thing well and thanks for the link