let say we have n
values
if there is a function that accepts an int n and if we want to find the mid of the value recursively?
we will use int mid = (leftSide rightSide) /2
. in which the leftSide
and the rightSide
might change according to the recursion values. However I found this not correct and the right one is
mid = leftSide (rightSide - leftSide)/2;
Can someone please explain the difference between those two. It might not be that hard question but I'm curious to know what the difference is.
CodePudding user response:
Using (leftSide rightSide) /2
can overflow, depending on the language and data types you are using and the values of leftSide
and rightSide
. The reason is that you first add leftSide
and rightSide
and then divide them by 2.
While in this method leftSide (rightSide - leftSide)/2
you subtract and divide them by 2 and then add leftSide, which can make a difference in some cases.
Other than that, those expressions are mathematically identical as follows:
leftSide (rightSide - leftSide)/2
2leftSide/2 (rightSide - leftSide)/2
(2leftSide rightSide - leftSide)/2
(rightSide leftSide)/2
CodePudding user response:
Notice that
(L R) / 2 = (L - R 2.R) / 2 = (L - R) / 2 R,
and
(L R) / 2 = (2.L - L R) / 2 = L (R - L) / 2.
using integer arithmetic.
Usually, L ≤ R
so that the difference L - R
is negative, and depending on the exact convention of the division in use, the quotient of (-1) / 2
might be -1
rather than 0
, an unexpected effect. The second form above is safer.