3 ms·
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 l
by stonemetal 17y ago
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.
- notaddicted 17y agoIf 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.
- ggchappell 17y ago> Assuming you used a signed integer for size .... By "integer", I did not mean "int". size was a std::size_t.