Thread: binsearch algorithm, weird division into intervals

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    44

    Question binsearch algorithm, weird division into intervals

    Hello, I have another question regarding K&R. In the following code I've marked the suspicious element:
    Code:
    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; /* here, I think +1 should be omitted */
            else if (x > v[mid])
                low = mid +1;
            else 
                return mid;
        }
        return -1;
    }
    Taking for example 15 as the size of an array v, high = 14. Then mid is 7, if x is smaller than v[7] then program creates new bound high which would be equal to 8. In that way the interval is now 0 to 8 (9 spaces in array). That is quite stupid for me since we already know that the eigth element doesn't satisfy the condition.
    If x is bigger than v[7] then low would be made equal to 8, new interval would be 8-14 (7 spaces in array).
    Correct me please if I'm wrong.
    Thanks in advance!

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Probably a typographical error. It should have been:
    Code:
    high = mid - 1;
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    44
    By the way, why do I need to pass size of an array (int n) to the function, isn't it already built-in into the argument of int v[] (since it has to be defined eg. as int v[20]) ?

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Pole
    By the way, why do I need to pass size of an array (int n) to the function, isn't it already built-in into the argument of int v[] (since it has to be defined eg. as int v[20]) ?
    No, because in binsearch, v is a pointer, not an array. Furthermore, what if you wanted to use this with an array named v1, of size 200?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by Pole View Post
    By the way, why do I need to pass size of an array (int n) to the function, isn't it already built-in into the argument of int v[] (since it has to be defined eg. as int v[20]) ?
    When you pass an array you really pass a pointer to the first element of the array. Thus the compiler doesn't know the size of the array.
    This is really an advantage because you can always pass an subarray to the function which makes the function more general/flexible.

    Bye, Andreas

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. binsearch function c programming language book
    By blob84 in forum C Programming
    Replies: 4
    Last Post: 05-17-2011, 04:36 AM
  2. Random numbers generator & Division algorithm
    By newclearner in forum C Programming
    Replies: 4
    Last Post: 10-06-2009, 12:48 PM
  3. Division Algorithm
    By author in forum C Programming
    Replies: 4
    Last Post: 04-15-2005, 12:02 PM
  4. Division Algorithm
    By -=neo=- in forum C++ Programming
    Replies: 2
    Last Post: 02-01-2005, 07:32 PM
  5. Division Algorithm
    By LuckY in forum C++ Programming
    Replies: 27
    Last Post: 11-15-2004, 10:20 AM