[arconis987]

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;

[benlivengood]

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)

[xxs]

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)

[linknoid]

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.

[nomy99]

can you explain to me how that fixes it? Thanks

[dan-robertson]

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.

[siawyoung]

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