4 ms·

can you explain to me how that fixes it? Thanks

• dan-robertson 6y ago
  There is an implicit invariant that 0 <= min, and min <= max, so max - min is between 0 and int_max inclusive, so you avoid overflowing with that calculation. To be sure that you avoid overflowing at the sum step, you need to prove that min + (max - min) / 2 <= max.
  • nomy99 6y ago
    what if max is already overflown due to size of array (without even doing the lo + high calculation?) Then min + (max- min)/2 would be min + (smaller negative value) which would violate the min + (max-min)/2 <= max
    • pk86 6y ago
      Assuming the value of max passed in is "sane" (non-negative and within array bounds), it is strictly decreasing and should never overflow.
• siawyoung 6y ago
  This makes sure that none of the quantities being calculated will overflow while still returning the same answer. Where x is min and y is max, the midpoint is: (x+y)/2 = x+(y-x)/2 x+y = 2x+y-x x+y=x+y