On Sun, 2006-06-04 at 14:41 -0700, Ben Maurer wrote:
> Hey,
> 
> This also exists for qsort
>         
>         object objPivot = keys.GetValueImpl ((low + high) / 2);

Good call.

Here's v2.

Duncan.
Index: System/ChangeLog
===================================================================
--- System/ChangeLog	(revision 61434)
+++ System/ChangeLog	(working copy)
@@ -1,3 +1,12 @@
+2006-06-04  Duncan Mak  <[EMAIL PROTECTED]>
+
+	* Array.cs (DoBinarySearch, BinarySearch<T>):
+	(qsort, qsort<K,V>, qsort<T>): Fixed the bug for finding the
+	average between 'low' and 'high', as pointed out by Joshua Bloch
+	in:
+
+	http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
+
 2006-06-01  Raja R Harinath  <[EMAIL PROTECTED]>
 
 	* Nullable.cs (operator==, operator!=): Remove.
Index: System/Array.cs
===================================================================
--- System/Array.cs	(revision 61434)
+++ System/Array.cs	(working copy)
@@ -644,7 +644,7 @@
 			int iCmp = 0;
 			try {
 				while (iMin <= iMax) {
-					int iMid = (iMin + iMax) / 2;
+					int iMid = iMin + ((iMax - iMin) / 2);
 					object elt = array.GetValueImpl (iMid);
 
 					iCmp = comparer.Compare (elt, value);
@@ -1270,7 +1270,7 @@
 			int low = low0;
 			int high = high0;
 
-			object objPivot = keys.GetValueImpl ((low + high) / 2);
+			object objPivot = keys.GetValueImpl (low + ((high - low) / 2));
 
 			while (low <= high) {
 				// Move the walls in
@@ -1468,7 +1468,7 @@
 			int low = low0;
 			int high = high0;
 
-			K keyPivot = keys [(low + high) / 2];
+			K keyPivot = keys [low + ((high - low) / 2)];
 
 			while (low <= high) {
 				// Move the walls in
@@ -1517,7 +1517,7 @@
 			int low = low0;
 			int high = high0;
 
-			T keyPivot = array [(low + high) / 2];
+			T keyPivot = array [low + ((high - low) / 2)];
 
 			while (low <= high) {
 				// Move the walls in
@@ -1832,7 +1832,7 @@
 			int iCmp = 0;
 			try {
 				while (iMin <= iMax) {
-					int iMid = (iMin + iMax) / 2;
+					int iMid = iMin + ((iMax - iMin) / 2);
 					iCmp = comparer.Compare (value, array [iMid]);
 
 					if (iCmp == 0)
Index: System.Collections/ChangeLog
===================================================================
--- System.Collections/ChangeLog	(revision 61434)
+++ System.Collections/ChangeLog	(working copy)
@@ -1,3 +1,11 @@
+2006-06-04  Duncan Mak  <[EMAIL PROTECTED]>
+
+	* ArrayList.cs (BinarySearch, QuickSort): Fixed the bug for
+	finding the average between 'low' and 'high', as pointed out by
+	Joshua Bloch in:
+
+	http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
+
 2006-04-26  Atsushi Enomoto  <[EMAIL PROTECTED]>
 
 	* Comparer.cs : changed internal field from CultureInfo to
Index: System.Collections/ArrayList.cs
===================================================================
--- System.Collections/ArrayList.cs	(revision 61434)
+++ System.Collections/ArrayList.cs	(working copy)
@@ -622,7 +622,7 @@
 
 				while (x <= y) 
 				{
-					z = (x + y) / 2;
+					z = x + ((y - x) / 2);
 				
 					r = comparer.Compare(value, m_Adaptee[z]);
 				
@@ -716,7 +716,7 @@
 
 				// Pick the pivot using the median-of-three strategy.
 
-				middle = (left + right) / 2;
+				middle = left + ((right - left) / 2);
 
 				if (comparer.Compare(list[middle], list[left]) < 0) 
 				{
_______________________________________________
Mono-devel-list mailing list
Mono-devel-list@lists.ximian.com
http://lists.ximian.com/mailman/listinfo/mono-devel-list

Reply via email to