By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,952 Members | 1,021 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,952 IT Pros & Developers. It's quick & easy.

Accelerated C++ exercise 8.8

P: n/a
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;
}

Apr 16 '06 #1
Share this Question
Share on Google+
8 Replies


P: n/a
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" <um********@gmail.com> wrote in message
news:11**********************@j33g2000cwa.googlegr oups.com...
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;
}

Apr 16 '06 #2

P: n/a
But is not that the case for the other as well??

Thx.

Apr 16 '06 #3

P: n/a
utab <um********@gmail.com> wrote:
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
--
jb

(reply address in rot13, unscramble first)
Apr 16 '06 #4

P: n/a
"utab" <um********@gmail.com> schrieb im Newsbeitrag news:11**********************@j33g2000cwa.googlegr oups.com...
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
Apr 16 '06 #5

P: n/a
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

"utab" <um********@gmail.com> wrote in message
news:11**********************@i39g2000cwa.googlegr oups.com...
But is not that the case for the other as well??

Thx.

Apr 16 '06 #6

P: n/a
"utab" <um********@gmail.com> wrote in message
news:11**********************@j33g2000cwa.googlegr oups.com...
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.
Apr 16 '06 #7

P: n/a
Now I know

Thx for the replies...

Apr 16 '06 #8

P: n/a
Jakob Bieling wrote:
utab <um********@gmail.com> wrote:
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.

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

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


Brian
Apr 16 '06 #9

This discussion thread is closed

Replies have been disabled for this discussion.