Question regarding the mid value used in the most searching and sorting algorithms. | Sololearn: Learn to code for FREE!
Nouvelle formation ! Tous les codeurs devraient apprendre l'IA générative !
Essayez une leçon gratuite
+ 6

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

" 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 ?

10th Apr 2021, 5:07 PM
Prince Gupta
Prince Gupta - avatar
11 Réponses
+ 10
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.
10th Apr 2021, 8:44 PM
ChaoticDawg
ChaoticDawg - avatar
+ 2
Thank You.
11th Apr 2021, 4:48 AM
Prince Gupta
Prince Gupta - avatar
+ 2
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.
13th May 2021, 2:00 PM
Vishal Pandey
11th Apr 2021, 3:14 AM
ChaoticDawg
ChaoticDawg - avatar
+ 1
Use binary sort ūüėé
12th May 2021, 11:43 AM
Sanjay Kamath
Sanjay Kamath - avatar
+ 1
It is recursive reduction .. that is why..
18th Oct 2021, 10:21 PM
Sanjay Kamath
Sanjay Kamath - avatar
0
May anyone provide me with an example ?
11th Apr 2021, 2:33 AM
Prince Gupta
Prince Gupta - avatar
0
good...to know this thing!!
16th Apr 2021, 6:25 PM
Molla Abbas
Molla Abbas - avatar
0
thnx for the help wil try apllying it
23rd Aug 2021, 9:08 AM
Sabelo Nqoba Mhlongo
0
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!!
3rd Jan 2022, 4:41 AM
Yash Shah
0
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.
7th Feb 2023, 4:12 AM
Manhar Hadiyal
Manhar Hadiyal - avatar