[Mono-dev] Patch for fixing binary search

Duncan Mak duncan at novell.com
Sat Jun 3 18:04:44 EDT 2006


Hello,

As pointed out by this blog post by Joshua Bloch:

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

The current by-the-book implementation of BinarySearch has an integer
overflow bug due to this:

	int mid = (low + high) / 2;

This bug manifests itself when (low + high) > Int32.MaxValue.

Here's a patch for fixing this in Array, Array<T> and ArrayList.

Duncan.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: fix-binary-search.patch
Type: text/x-patch
Size: 2272 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20060603/67cf1df2/attachment.bin 


More information about the Mono-devel-list mailing list