[Mono-dev] Patch for fixing binary search

Ben Maurer bmaurer at ximian.com
Sun Jun 4 17:41:46 EDT 2006


Hey,

This also exists for qsort
        
        object objPivot = keys.GetValueImpl ((low + high) / 2);

-- Ben

On Sat, 2006-06-03 at 18:04 -0400, Duncan Mak wrote:
> 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.
> _______________________________________________
> Mono-devel-list mailing list
> Mono-devel-list at lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-devel-list




More information about the Mono-devel-list mailing list