CODEWITHSUNDEEP
algorithmdivide-and-conquer
John Doe
John Doe

Reputation: 400

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

For a divide and conquer algorithm in an array, we need to be able to find the middle element of a range. The obvious way to do that is mid = (leftSide + rightSide) / 2. However, I've heard that that way is not correct, and that we need to write mid = leftSide + (rightSide - leftSide) / 2 instead. Can someone explain the difference between those two?

Upvotes: 1

Views: 119

Answers (2)

user1196549
user1196549

Reputation:

Notice that for all L and R,

(L + R) / 2 = (2.L - L + R) / 2 = L + (R - L) / 2.

using integer arithmetic. Hence there is no difference (except in case of overflow or negative numbers; then even division by 2 or right-shift may yield different results).

Upvotes: 0

user1984
user1984

Reputation: 6818

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

On request of OP, I am adding a concrete Java example on how (leftSide + rightSide) / 2 can overflow.

Suppose we are storing left and right in java ints which are 4 byte signed integers. This means that they cover -2^31 to 2^31-1. Now, further suppose that we have 0 and 2147483000 as our left and right. Keep in mind that our upper bound is only slightly less than the 4 byte signed integer's upper limit of 2^31-1 = 2147483647. After the first search, since target lies on the right side, left becomes 1073741501, because 2147483000 / 2 + 1 = 1073741501. Now at this point using the formula (left + right) / 2 is dangerous. Because:

left =  2147483000 / 2 + 1 = 1073741501
right = 2147483000
left + right = 3221224501

So, left + right is above the available limit/bits for an unsigned 4 byte integers. What happens is that Java interprets the new integers as negative since the most significant bit which shows the sign is set. Consider the following example:

public class Main
{
    public static void main(String[] args) {
        
        int right = 2147483647;
        int left = 1073741500;
        
        System.out.println(left + " " + right);
        System.out.println(left + right);
    }
}

Outputs:

1073741500 2147483647
-1073742149

Long story short, you can avoid this situation by using leftSide + (rightSide - leftSide)/2. Since you subtract left from right first and the divide by 2, there is no risk of overflow.

If you are further interested, here's a blog post by a Google Research engineer on how prevalent this bug in binary search is.

Upvotes: 5

Related Questions