424,952 Members | 1,021 Online
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 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
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" 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 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 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" 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" 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" 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 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: Brian Apr 16 '06 #9

### This discussion thread is closed

Replies have been disabled for this discussion.