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.
[ Parent
| on HN ]
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.