Question regarding the mid value used in the most searching and sorting algorithms.

Question

" The safest way to find the middle of two numbers without getting an overflow is as follows: mid = start + (end-start)/2 "
Why it can't be mid = (start + end) / 2 ?

Answer 1

start + (end - start) / 2
Is preferred because there is a possibility in a very large array that the result from (start + end) could cause an integer overflow where the resulting value is larger than the max value for int. This would end up in a negative value, causing the index to be out of the bounds of the array.

Answer 2

Thank You.

Answer 3

it is same, m = (l+r)/2

you should know what it does, In array it takes the array indices and then it find the mid value on its basis we access the mid position's value.

let l = start, r = end, m = mid;
m = l + (r-l)/2 = l + r/2 - l/2 = l/2+r/2 = (l+r)/2.

That's how the fancy formula is straight forward written.

Answer 4

https://code.sololearn.com/c9aYXjD55L6E/?ref=app

Answer 5

Use binary sort 😎

Answer 6

It is recursive reduction .. that is why..

Answer 7

May anyone provide me with an example ?

Answer 8

good...to know this thing!!

Answer 9

thnx for the help wil try apllying it

Answer 10

Hey There!!!
mid = (start + end) / 2 could be done but it is definitely not a recommended way since there could be some cases where starting index i.e [0] and the last index [n] could be very large. Hence, the value of mid in those cases could overshoot the higher constraint. Hence, to deal with such special cases with much more efficiency and no errors, it is recommended to make use of the following equation to calculate mid value:
mid = start + (end-start)/2

Thank You!!
All the Best!!

Answer 11

The expression (start + end) / 2 may cause an overflow if the sum of start and end exceeds the maximum value that can be stored in the data type being used (such as int in many programming languages). In such a case, the result of the expression would wrap around and become a negative value, which could lead to incorrect results.

On the other hand, the expression start + (end - start) / 2 is guaranteed to not overflow, as it first subtracts start from end to obtain the difference, and then divides it by 2, before finally adding it back to start. This way, the value of mid will always be within the range of start and end, without the risk of overflow.