+ 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 Answers
+ 9
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
Sabelo Nqoba Mhlongo - avatar
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
If you've observed, the time complexity of Quicksort is O(n logn) in the best and average case scenarios and O(n^2) in the worst case. But since it has the upper hand in the average cases for most inputs, Quicksort is generally considered the “fastest” sorting algorithm.
3rd Jan 2023, 7:27 AM
Joanne Garrett