Isn't version 2 wrong, because
size_t probe = (low + high) / 2;
size_t probe = (low + high) / 2;
They are using signed integers as their indices, which means that the signed bit is always 0. Thus the addition after casting to unsigned will never overflow, and you can divide by two (shift by 1) and then recast to a signed integer, no harm no foul.
In other words, C allows that UINT_MAX == INT_MAX, in which case you will overflow.
If they made that assumption, they should explicitly mention it, but they didn't.
> Update 17 Feb 2008:... ...Now that we've made this change, we know that the program is correct;)
It seems the article is aware of the irony. Another update would be in order.
Also I'm not trying to mislead people into thinking that its a good way to implement this. The confounding bit from the article is they started in Java and ended up in C. If you were indexing with signed ints in C, C++, or any language that has unsigned integers then you already have a bug with or without the bad mean check.
suppose low is M-3 and high is M-1 (where M is 2^[#bits]) then mid should be M-2. but (M-3 + M-1) is (modulo M) equal to M-4. and half that is M/2 - 2, which is a lot less than the correct M-2. (pretend it's 2 bit unsigned ints so M is 4)
the correct 'mid' computation is low + (high - low)/2.
In practise that's not possible if it contains 32-bit integers because that would take up a 16 GB linear address space which doesn't exist on a 32-bit machine.
An academically correct version would be `size_t probe = low + ((high - low) / 2);` but that would be much slower.
You could instead just add an initial debug-mode-only assert on the list length, for correctness.