5 ms·

This is my go-to implementation, but I make one little tweak. It’s very unlikely that you will overflow a long, but you can you guarantee that you’ll avoid over

This is my go-to implementation, but I make one little tweak. It’s very unlikely that you will overflow a long, but you can you guarantee that you’ll avoid overflow like this: mid = min + (max - min) / 2;

nomy99 6y ago
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
linknoid 6y ago
That's my C# implementation, so long is 64 bits and int is 32 bits. 64 bits will never overflow in my lifetime. That's basically a Google scale amount of data.
xxs 6y ago
If the unsigned right shift is defined (java): "int mid = (min + max) >>> 1;" edit: this is a bit longer version, if signed conversion/shift is not available: int mid = (min >> 1) + (max >> 1) + (min & max & 1)
benlivengood 6y ago
In x86 (intel notation) you can also: add rax, rbx rcr rax, 1 It explicitly uses the carry flag from the addition as the top bit of the right-rotated result. Not super useful for anything other than averaging two uints but that's x86 for you. What I missed in my first pass was * Forgetting exactly which register was the low index and which was the high index * Underflow if array size was zero from setting the last index to (size - 1)

nomy99 6y ago

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

linknoid 6y ago

That's my C# implementation, so long is 64 bits and int is 32 bits. 64 bits will never overflow in my lifetime. That's basically a Google scale amount of data.

xxs 6y ago

If the unsigned right shift is defined (java): "int mid = (min + max) >>> 1;" edit: this is a bit longer version, if signed conversion/shift is not available: int mid = (min >> 1) + (max >> 1) + (min & max & 1)

benlivengood 6y ago

In x86 (intel notation) you can also: add rax, rbx rcr rax, 1 It explicitly uses the carry flag from the addition as the top bit of the right-rotated result. Not super useful for anything other than averaging two uints but that's x86 for you. What I missed in my first pass was * Forgetting exactly which register was the low index and which was the high index * Underflow if array size was zero from setting the last index to (size - 1)