News for hackers. Stuff that matters.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by stonemetal on Wednesday February 17, 2010 @09:14AM (#1131528)
How does that avoid the problem? Assuming you used a signed integer for size and the list is large enough, there is a sign roll over on size. If size becomes less than -2 then low + size/2 is less than low (on the first pass of a binary search you now have an invalid iterator for mid). Assuming you used unsigned integers size can still not be the correct value if a rollover has occurred though this time mid will always be valid.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by notaddicted on Wednesday February 17, 2010 @10:48AM (#1131693)
If you have a byte array on a 32bit machine, assuming your program's text (i.e. instructions) takes up some space, the biggest possible array will be less than 2^32 Bytes = 4GiB, so the midpoint will be too. There can be no overflow.

If you subtracted two 64bit pointers and stored the result in an int32 though, then you would have problems.

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by ggchappell on Wednesday February 17, 2010 @08:47PM (#1133195)
> Assuming you used a signed integer for size ....

By "integer", I did not mean "int". size was a std::size_t.