Fix binary search middle calculation to avoid overflows
MODIFY
thrust/system/detail/generic/scalar/binary_search.inl
thrust/system/detail/generic/scalar/binary_search.inl
@@ -52,7 +52,7 @@ RandomAccessIterator lower_bound_n(RandomAccessIterator first,
Size start = 0, i;
while(start < n)
{
- i = (start + n) / 2;
+ i = start + (n - start) / 2; // Overflow-safe variant of (a+b)/2
if(wrapped_comp(first[i], val))
{
start = i + 1;
@@ -94,7 +94,7 @@ RandomAccessIterator upper_bound_n(RandomAccessIterator first,
Size start = 0, i;
while(start < n)
{
- i = (start + n) / 2;
+ i = start + (n - start) / 2; // Overflow-safe variant of (a+b)/2
if(wrapped_comp(val, first[i]))
{
n = i;
@@ -156,4 +156,3 @@ bool binary_search(RandomAccessIterator first, RandomAccessIterator last, const
} // end thrust
#include <thrust/system/detail/generic/scalar/binary_search.inl>
-

Fix binary search middle calculation to avoid overflows