If I am not mistaken, when the list gets very large (might require 64bit OS and a large amount of ram), the line calculating the guess can overflow:
int guess = (left + right) >> 1;
For example, if the size is 2^31 - 1, and we provide a key that is in
the top half, the loop will go as follow: left = 0, right = 2^31 - 2,
guess = ~2^30. if cmp < 0, left becomes ~2^30 and on the next
iteration, left + right will be (2^31 - 2 + ~2^30) which is larger
than int.MaxValue (2^31-1) thus causing overflow before the right
shift to divide by 2.
See also this link for a similar issue in a java container method:
This is a very common problem with binary search implementations.