a mistake in the c programming language book.wtf?

This is a discussion on a mistake in the c programming language book.wtf? within the C Programming forums, part of the General Programming Boards category; 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 ...

  1. #1
    Registered User
    Join Date
    Sep 2005
    Posts
    46

    a mistake in the c programming language book.wtf?

    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...
    Code:
    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.

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    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...

  3. #3
    Registered User
    Join Date
    Sep 2005
    Posts
    46
    i have the ebook and its the second edition........anyway its in chapter 2 the if else part

  4. #4
    Rabble Rouser Slacker's Avatar
    Join Date
    Dec 2005
    Posts
    116
    >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!

  5. #5
    Registered User
    Join Date
    Jun 2005
    Location
    Stockholm, Sweden
    Posts
    64
    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:
    Code:
    /* 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?

  6. #6
    Registered User
    Join Date
    Sep 2005
    Posts
    46
    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

  7. #7
    Registered User
    Join Date
    Jun 2005
    Location
    Stockholm, Sweden
    Posts
    64
    Huh? If the target is found, then the index of the target is returned. If the target is not found, -1 is returned.

  8. #8
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  9. #9
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,496
    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

  10. #10
    Registered User
    Join Date
    Sep 2005
    Posts
    46
    thanks guys seems i didnt understand the return thing well and thanks for the link

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. assembly language...the best tool for game programming?
    By silk.odyssey in forum Game Programming
    Replies: 50
    Last Post: 06-22-2004, 01:11 PM
  2. Language of choice after C++
    By gandalf_bar in forum A Brief History of Cprogramming.com
    Replies: 47
    Last Post: 06-15-2004, 01:20 AM
  3. Enough language discussions.
    By VirtualAce in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 06-13-2004, 09:59 AM
  4. Another new language? F sharp (F#)
    By XenoCodex Admin in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 07-07-2002, 03:20 PM
  5. Most Impacting/Powerful Future Programming Language
    By kuphryn in forum C++ Programming
    Replies: 11
    Last Post: 12-07-2001, 02:46 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21