JDK-6412541 : Arrays.binarySearch does not work for arrays larger than 1<<30
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util
  • Affected Version: 6
  • Priority: P3
  • Status: Closed
  • Resolution: Duplicate
  • OS: generic
  • CPU: generic
  • Submitted: 2006-04-12
  • Updated: 2010-04-02
  • Resolved: 2006-04-15
Related Reports
Duplicate :  
JDK-5045582 - (coll) binarySearch() fails for size larger than 1<<30
Description
Various binary search methods in java.util.Arrays compute the average of
two positive indices (ints) like this:

	    int mid = (low + high) >> 1;

but if low + high overflows into negative territory, the result is negative,
probably giving undefined results.  An easy fix is the simple


	    int mid = (low + high) >>> 1;

although I have not tested whether this is enough to get sort + binary search 
to actually work properly on such gigantic arrays.
Comments
EVALUATION A clean test case: import java.util.*; public class Bug { public static void main(String[] args) throws Throwable { int n = (1<<30) + 7; byte[] big = new byte[n]; big[n - 1] = (byte) 43; big[n - 2] = (byte) 42; int s = Arrays.binarySearch(big, (byte) 42); if (n - s != 2) throw new Error(); } } $ jver mustang jr -Xmx1600m -d32 Bug ==> javac -source 1.6 -Xlint:all Bug.java ==> java -Xmx1600m -d32 -esa -ea Bug Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1073741822 at java.util.Arrays.binarySearch(Arrays.java:1499)
13-04-2006
SUGGESTED FIX --- /u/martin/ws/mustang/src/share/classes/java/util/Arrays.java 2006-01-30 15:30:55.393345000 -0800 +++ /u/martin/ws/binarySearch/src/share/classes/java/util/Arrays.java 2006-04-12 17:47:07.595416000 -0700 @@ -1153,7 +1153,7 @@ int destHigh = high; low += off; high += off; - int mid = (low + high) >> 1; + int mid = (low + high) >>> 1; mergeSort(dest, src, low, mid, -off); mergeSort(dest, src, mid, high, -off); @@ -1281,7 +1281,7 @@ int destHigh = high; low += off; high += off; - int mid = (low + high) >> 1; + int mid = (low + high) >>> 1; mergeSort(dest, src, low, mid, -off, c); mergeSort(dest, src, mid, high, -off, c); @@ -1342,7 +1342,7 @@ int high = a.length-1; while (low <= high) { - int mid = (low + high) >> 1; + int mid = (low + high) >>> 1; long midVal = a[mid]; if (midVal < key) @@ -1381,7 +1381,7 @@ int high = a.length-1; while (low <= high) { - int mid = (low + high) >> 1; + int mid = (low + high) >>> 1; int midVal = a[mid]; if (midVal < key) @@ -1419,7 +1419,7 @@ int high = a.length-1; while (low <= high) { - int mid = (low + high) >> 1; + int mid = (low + high) >>> 1; short midVal = a[mid]; if (midVal < key) @@ -1457,7 +1457,7 @@ int high = a.length-1; while (low <= high) { - int mid = (low + high) >> 1; + int mid = (low + high) >>> 1; char midVal = a[mid]; if (midVal < key) @@ -1495,7 +1495,7 @@ int high = a.length-1; while (low <= high) { - int mid = (low + high) >> 1; + int mid = (low + high) >>> 1; byte midVal = a[mid]; if (midVal < key) @@ -1535,7 +1535,7 @@ private static int binarySearch(double[] a, double key, int low,int high) { while (low <= high) { - int mid = (low + high) >> 1; + int mid = (low + high) >>> 1; double midVal = a[mid]; int cmp; @@ -1588,7 +1588,7 @@ private static int binarySearch(float[] a, float key, int low,int high) { while (low <= high) { - int mid = (low + high) >> 1; + int mid = (low + high) >>> 1; float midVal = a[mid]; int cmp; @@ -1648,7 +1648,7 @@ int high = a.length-1; while (low <= high) { - int mid = (low + high) >> 1; + int mid = (low + high) >>> 1; Comparable midVal = (Comparable)a[mid]; int cmp = midVal.compareTo(key); @@ -1701,7 +1701,7 @@ int high = a.length-1; while (low <= high) { - int mid = (low + high) >> 1; + int mid = (low + high) >>> 1; T midVal = a[mid]; int cmp = c.compare(midVal, key);
13-04-2006
EVALUATION The submitter appears to be correct. Got to find a 64-bit machine with a few spare GB of RAM for some testing. $ cat hh.java && jver 6 jr hh public class hh { public static void main(String[] args) throws Throwable { int lo = (1<<30) + 16; int hi = lo + 2; for (int x : new int[]{lo, hi, (lo+hi)>>1, (lo+hi)>>>1}) System.out.println(x); } } ==> javac -source 1.6 -Xlint:all hh.java ==> java -esa -ea hh 1073741840 1073741842 -1073741807 1073741841
12-04-2006