Home > Net >  What is the difference between finding the mid in the following two different ways
What is the difference between finding the mid in the following two different ways

Time:11-26

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.

  • Related