United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
JDK-6412541 : Arrays.binarySearch does not work for arrays larger than 1<<30

Details
Type:
Bug
Submit Date:
2006-04-12
Status:
Closed
Updated Date:
2010-04-02
Project Name:
JDK
Resolved Date:
2006-04-15
Component:
core-libs
OS:
generic
Sub-Component:
java.util
CPU:
generic
Priority:
P3
Resolution:
Duplicate
Affected Versions:
6
Fixed Versions:

Related Reports
Duplicate:

Sub Tasks

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)
                                     
2006-04-13
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);
                                     
2006-04-13
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
                                     
2006-04-12



Hardware and Software, Engineered to Work Together