Binary Search Reconsidered (2018)

Re:Binary Search Reconsidered (2018) by dan-robertson on Friday December 25, 2020 @12:45PM (#25537841)

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.

[ Parent | on HN ]

Re:Binary Search Reconsidered (2018) by nomy99 on Friday December 25, 2020 @01:11PM (#25538004)

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

[ Parent | on HN ]

Re:Binary Search Reconsidered (2018) by pk86 on Friday December 25, 2020 @01:35PM (#25538126)

Assuming the value of max passed in is "sane" (non-negative and within array bounds), it is strictly decreasing and should never overflow.

[ Parent | on HN ]