CODEWITHSUNDEEP
algorithmoverflowbinary-search
q0987
q0987

Reputation: 35982

Why this binary search implementation causes overflow?

In the implementation of binary search

int search(int[] A, int K) {
  int l = 0;
  int u = A.length - 1;
  int m
  while ( l <= u ) {
     m = (l+u)/2; // why this can cause overflow
     ...
  }
}

The correct method is as follows:

m = l + (u -l )/2;

I don't know why the updated statement has no overflow issue. Based on my understanding, soon or later, the updated statement will also have overflow issue.

Upvotes: 0

Views: 330

Answers (2)

Anupam Haldkar
Anupam Haldkar

Reputation: 1085

The initial Calculation of m = (l+u)/2 create overflow due to addition of very large numbers. So, Difference of these numbers does not cause this overflow condition ,that's why we are calculating m=l+(u-l)/2 using this formula.

Upvotes: 0

Peter Alexander
Peter Alexander

Reputation: 54270

The orignal may have overflow because l+u could be greater than the maximum value an int can handle (e.g. if both l and u were INT_MAX then their sum would obviously exceed INT_MAX).

The correct method can't overflow, because u-l obviously won't overflow, and l+(u-l)/2 is guaranteed to be <=u, so can't overflow either.

Upvotes: 4

Related Questions