Accelerated C++ exercise 8.8

[utab]

Dear all, in a container example, this question is asked in exercises
in Accelerated C++ page 154, 8.8? why dont we use (begin+end)/2 instead
of begin + (end - begin) / 2 is that someting related with the
algortihm

if you take a vector lets say

begin end (one past the last)
| |
1 2 3 4 4 6 7 8 9

(begin+end)/2 returns the iter for the 2nd 4.

if you take a vector lets say

begin end (one past the last)
| |
1 2 3 4 4 6 7 8 9 10

(begin+end)/2 returns the iter for the 6.

So this looks right to me also but could not figure out.




template <class Ran, class X>
bool binary_search(Ran begin, Ran end, const X& x)
{
while (begin < end) {
// find the midpoint of the range
Ran mid = begin + (end - begin) / 2; // why dont we use
(begin+end)/2 instead

// see which part of the range contains `x'; keep looking only
in that part
if (x < *mid)
end = mid;
else if (*mid < x)
begin = mid + 1;
// if we got here, then `*mid == x' so we're done
else return true;
}
return false;
}

 

[Moonlit]

Hi,

Well for one thing, begin + end might overflow the maximum value of the
pointer type. Say begin points to FFFFFF0 and end to FFFFFFF4 and assuming
a 32 bit pointer then (begin + end)/2 would be uuhm... well anyway it would
be the wrong address.

--


Regards, Ron AF Greve

http://moonlit.xs4all.nl

 

[utab]

But is not that the case for the other as well??

Thx.

 

[Jakob Bieling]

But is not that the case for the other as well??

What other? What are you replying to? Please quote correctly:
http://www.netmeister.org/news/learn2quote.html.

Overflow can happen for indeces as well as for pointers and
iterators (which may be pointers under the hood). Also note that you
cannot add pointers, as the addition (alone) will not make sense. Same
applies to iterators. If that is what you meant.


hth

 

[Heinz Ozwirk]

Dear all, in a container example, this question is asked in exercises
in Accelerated C++ page 154, 8.8? why dont we use (begin+end)/2 instead
of begin + (end - begin) / 2 is that someting related with the
algortihm

Why? Because begin + end doesn't even compile. What is the sum of two iterators? What is the sum of two pointers? What is the sum of New York and San Diego? And what is half that sum? You can calculate the distance from New York to San Diego, and if you know the distance, you will know what is in the middle between New York and San Diego. And basically it's the same with two iterators or pointers. You cannot add them, you can only measure their distance.

HTH
Heinz

 

[Moonlit]

Hi,

No, because you substract and then add the difference to the other pointer,
because of the limited storage the two calculations though mathematically
the same will not lead to the same result (besides the fact that it is not
allowed as other noted in this thread) However I find it eassier to remember
those things if know some reason behind it.

Assume your pointer size is just a byte and do the two calculations
yourself, make sure to take overflowing the byte in account.

--


Regards, Ron AF Greve

http://moonlit.xs4all.nl

 

[Andrew Koenig]

Dear all, in a container example, this question is asked in exercises
in Accelerated C++ page 154, 8.8? why dont we use (begin+end)/2 instead
of begin + (end - begin) / 2 is that someting related with the
algortihm

if you take a vector lets say

begin end (one past the last)
| |
1 2 3 4 4 6 7 8 9

(begin+end)/2 returns the iter for the 2nd 4.

I suggest you try it for yourself and see what happens.

 

[utab]

Now I know

Thx for the replies...

 

[Default User]

What other? What are you replying to? Please quote correctly:
http://www.netmeister.org/news/learn2quote.html.

As "utab" is using Google, the information here may help:

<http://cfaj.freeshell.org/google/>




Brian