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?

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.

Quote:

y must point to an item with a higher or equal memory address than x...

Quote:

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)?

Quote:

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() ).

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:

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).

Quote:

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

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?

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.

Quote:

How do you denote an empty range?

Possibly; null pointers in x and y.

Quote:

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;

Actually you have a point. At the moment it should actually work if x > y.

Quote:

Originally Posted by iMalc

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 )
:)