A common mistake when writing binary search is to allow possible
integer overflow by using the simple average:
mid = (min + max) / 2;
Instead, use the overflow-safe version:
mid = min + (max - min) / 2;
The included changes were found using the following two greps:
grep
On Fri, Oct 06, 2017 at 09:52:31AM -0400, Derrick Stolee wrote:
> A common mistake when writing binary search is to allow possible
> integer overflow by using the simple average:
>
> mid = (min + max) / 2;
>
> Instead, use the overflow-safe version:
>
> mid = min + (max - min) / 2;
On 10/6/2017 10:18 AM, Jeff King wrote:
On Fri, Oct 06, 2017 at 09:52:31AM -0400, Derrick Stolee wrote:
A common mistake when writing binary search is to allow possible
integer overflow by using the simple average:
mid = (min + max) / 2;
Instead, use the overflow-safe version:
Calculating the sum of two array indexes to find the midpoint between
them can overflow, i.e. code like this is unsafe for big arrays:
mid = (first + last) >> 1;
Make sure the intermediate value stays within the boundaries instead,
like this:
mid = first + ((last - first) >> 1);
On 6/13/2019 1:51 PM, René Scharfe wrote:
> Calculating the sum of two array indexes to find the midpoint between
> them can overflow, i.e. code like this is unsafe for big arrays:
>
> mid = (first + last) >> 1;
>
> Make sure the intermediate value stays within the boundaries instead,
> lik
On Thu, 13 Jun 2019 at 19:54, René Scharfe wrote:
>
> Calculating the sum of two array indexes to find the midpoint between
> them can overflow, i.e. code like this is unsafe for big arrays:
>
> mid = (first + last) >> 1;
>
> Make sure the intermediate value stays within the boundaries ins
Am 13.06.19 um 21:42 schrieb Martin Ågren:
> On Thu, 13 Jun 2019 at 19:54, René Scharfe wrote:
>>
>> Calculating the sum of two array indexes to find the midpoint between
>> them can overflow, i.e. code like this is unsafe for big arrays:
>>
>> mid = (first + last) >> 1;
>>
>> Make sure th
On Thu, 13 Jun 2019 at 23:33, René Scharfe wrote:
>
> Am 13.06.19 um 21:42 schrieb Martin Ågren:
> > On Thu, 13 Jun 2019 at 19:54, René Scharfe wrote:
> >> Make sure the intermediate value stays within the boundaries instead,
> >> like this:
> >>
> >> mid = first + ((last - first) >> 1);
8 matches
Mail list logo