Notice (2018-05-24): bugzilla.xamarin.com is now in
Please join us on
Visual Studio Developer Community and in the
Mono organizations on
GitHub to continue tracking issues. Bugzilla will remain
available for reference in read-only mode. We will continue to work
on open Bugzilla bugs, copy them to the new locations
as needed for follow-up, and add the new items under Related
Our sincere thanks to everyone who has contributed on this bug
tracker over the years. Thanks also for your understanding as we
make these adjustments and improvements for the future.
Please create a new report for Bug 4328 on
GitHub or Developer Community if you have new
information to add and do not yet see a matching new report.
If the latest results still closely match this report, you can use the
In special cases on GitHub you might also want the comments:
GitHub Markdown with public comments
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.