Like Tree3Likes
  • 1 Post By laserlight
  • 1 Post By laserlight
  • 1 Post By AndiPersti

binsearch algorithm, weird division into intervals

This is a discussion on binsearch algorithm, weird division into intervals within the C Programming forums, part of the General Programming Boards category; Hello, I have another question regarding K&R. In the following code I've marked the suspicious element: Code: int binsearch(int x, ...

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

    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
    21,445
    Probably a typographical error. It should have been:
    Code:
    high = mid - 1;
    Pole likes this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    39
    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
    21,445
    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?
    Pole likes this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    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
    Pole likes this.

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, 06:32 PM
  5. Division Algorithm
    By LuckY in forum C++ Programming
    Replies: 27
    Last Post: 11-15-2004, 09:20 AM

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