Thread: Returning a pointer in Binary Search

  1. #1
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657

    Returning a pointer in Binary Search

    I'm almost sure that this does not result in undefined behaviour as what I'm returning is within range of the supplied pointers.
    Still..there may be something I'm not aware of.
    <I'm aware of <algorithm> but this is for a homework >

    Code:
    int* bin_s(int n,int* x, int* y)
    {
        if(x==y)
            if(*x==n)
                return x;
            else return 0;
        else if (y-x==1||x-y==1)
        {
            if(n==*x)return x;
            else if(n==*y)return y;
            else return 0;
        }
        else
        {
            int* temp = x+((y-x)/2);
            int* result;
            if(n>= *temp)
                result = bin_s(n,temp,y);
            else
                result = bin_s(n,x,temp);
            return result;
        }
    
    }
    Does it seem okay?
    Last edited by manasij7479; 09-11-2011 at 10:50 PM.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You shouldn't need to check for x-y==1 because x should never be greater than y.

    Also, add brackets round your first if-statement. Don't leave the reader able to accidentally think that the else corresponds to the outer if rather than the inner one.

    There is no undefined behaviour in that code. Looks like it should all work to me. Just make sure you call it with the right values. In this case you need to pass a pointer to the last element as y rather than the more convient and optimal one-past-the-end.

    You could always try and do it iteratively instead of recursively if you're keen to learn a bit more.

    One thing that would be good to add to the comments of this function are that x and y must both be non-null, and in fact y must point to an item with a higher or equal memory address than x, and from within the same array. The code could check for NULL itself rather than relying on the documentation of the function, but the rest of that precondition is not something that you can validate from the code without invoking undefined behaviour according to the standard. So if it we me, I'd just document it.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    y must point to an item with a higher or equal memory address than x...
    x should never be greater than y
    Though I'm not likely to use anything other than a x86...Isn't that system dependent (and could become just the reverse)?

    In this case you need to pass a pointer to the last element as y rather than the more convient and optimal one-past-the-end.
    I did not follow the 'one-past-the-end' convention..as in the STL iterators' end() function because I had no simple way to control what lay beyond the end here. (AFAIK.. those iterators put some thing which throws an exception if dereferenced at the end() ).

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by manasij7479
    Though I'm not likely to use anything other than a x86...Isn't that system dependent (and could become just the reverse)?
    You're doing pointer arithmetic, not arithmetic with memory address values. If you were really subtracting memory address values, then you would have written x-y==sizeof(int) instead. So, whatever the value the address of the memory, the relative value of the pointers in C++ is such that x <= y.

    Quote Originally Posted by manasij7479
    I did not follow the 'one-past-the-end' convention..as in the STL iterators' end() function because I had no simple way to control what lay beyond the end here.
    You do not need to control that in the first place.

    Quote Originally Posted by manasij7479
    (AFAIK.. those iterators put some thing which throws an exception if dereferenced at the end() ).
    They might do that to aid error detection and debugging, but there is no such requirement.
    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
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    You do not need to control that in the first place.
    ...So I didn't include it so that I do not cause accidents with the end value...(I recently had some trouble tracking a problem originating from using < instead of <= in a loop).

    . If you were really subtracting memory address values, then you would have written x-y==sizeof(int) instead.
    Thanks, I was somewhat confused about the distinction between the two.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by manasij7479
    So I didn't include it so that I do not cause accidents with the end value.
    You can cause accidents either way. How do you denote an empty range? What if you want to generalise your algorithm to use say, forward iterators instead of only random access iterators?
    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

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Code:
    int* bin_s(int n,int* x, int* y)
    {
        int* result = NULL;
        if(x==y)
            if(*x==n)
                result = x;
            else result = 0;
        else if (y-x==1||x-y==1)
        {
            if(n==*x) result = x;
            else if(n==*y) result = y;
            else result = 0;
        }
        else
        {
            int* temp = x+((y-x)/2);
            if(n>= *temp)
                result = bin_s(n,temp,y);
            else
                result = bin_s(n,x,temp);
        }
        return result;
    If you have lots of returns in the middle of the code, you risk missing a case and falling off the end of the function with a garbage value.


    You could also have added an explicit
    return NULL;
    at the end as well.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  8. #8
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    How do you denote an empty range?
    Possibly; null pointers in x and y.
    What if you want to generalise your algorithm to use say, forward iterators instead of only random access iterators?
    In this context..
    if (generalise == change)
    It seems I only have to change this assignment.
    Code:
    int* temp = x+((y-x)/2);
    else I have no idea;

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Actually you have a point. At the moment it should actually work if x > y.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by iMalc View Post
    Actually you have a point. At the moment it should actually work if x > y.
    Though it wasn't my intention... I was quite surprised by that... (especially accidentally&&accurately calculating the middle point pointer when x>y )

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 02-28-2010, 10:35 PM
  2. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  3. Search Engine - Binary Search Tree
    By Gecko2099 in forum C Programming
    Replies: 9
    Last Post: 04-17-2005, 02:56 PM
  4. Replies: 41
    Last Post: 07-04-2004, 03:23 PM
  5. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 10:18 AM