Returning a pointer in Binary Search

This is a discussion on Returning a pointer in Binary Search within the C++ Programming forums, part of the General Programming Boards category; I'm almost sure that this does not result in undefined behaviour as what I'm returning is within range of the ...

  1. #1
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498

    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.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    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
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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() ).
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    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.
    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 manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    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?
    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

  7. #7
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,418
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  8. #8
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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;
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    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
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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 )
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 02-28-2010, 09:35 PM
  2. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 01: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, 09:18 AM

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