This, of course, is why you always use size_t for array indices. (unsigned int blows up on amd64, too: a 4GB array of chars is huge but not impossibly large).
That wouldn't have helped in this case, since the issue was an overflow in the (high+low) / 2 calculation. Wouldn't using size_t just make the problem less likely to happen (requiring an even larger array to show up)?
The C Stardard (addmittedly from ISO:9899:1990, which describes C89; it still holds for C99; no comment on C++, which I don't use) states: "... size_t which is the unsigned integral type of the result of the sizeof operator ..."
P. J. Plauger in _The Standard C Library_ states: "When you apply the sizeof operator in a C expression, the result has type size_t. It is an unsigned integer type that can represent the size of the largest data object you can declare. Almost certainly it is either unsigned int or unsigned long. [emphasis in original] ... It is the safest type to represent any integer data object you use as an array subscript. You don't have to worry if a small array evolves to a vary large one as the program changes. Subscript arithmetic will never overflow when performed in type size_t. You don't have to worry if the program moves to a machine with peculiar properties, such as 32-bit bytes and 1-byte longs. Type size_t offers the greatest chance that your code won't be unduly surprised. The only sensible type to use for computing the sizes of data object is size_t. ... You should make a point of using type size_t anywhere [emphasis in original] your program performs array subscripting or address arithmetic."
Answer as I see it: the issue wouldn't come up at all.
That's all true, but unfortunately it doesn't help. You can still have two indices greater than half the maximum value of a size_t, and cause an overflow.
The problem here isn't the maximum value of whatever data type we are using, it is that no matter what that maximum is, you can always exceed it by adding two sufficiently large values of that same type together.
I'm sorry, I spoke too quickly. On the other hand, it would actually have worked: every OS I'm aware of (Windows, Linux, OpenBSD) limits 32-bit applications to 2GB of memory, and 64-bit applications to some ridiculously large number well short of 2^64. In neither case could this actually overflow.
But that's system-specific; it's not defined to fix this, so sorry for spreading the misinformation.
