United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
JDK-5045582 : (coll) binarySearch() fails for size larger than 1<<30

Details
Type:
Bug
Submit Date:
2004-05-11
Status:
Closed
Updated Date:
2012-10-08
Project Name:
JDK
Resolved Date:
2006-04-29
Component:
core-libs
OS:
generic,linux
Sub-Component:
java.util:collections
CPU:
generic,x86
Priority:
P2
Resolution:
Fixed
Affected Versions:
5.0,6
Fixed Versions:

Related Reports
Duplicate:
Relates:
Relates:
Relates:

Sub Tasks

Description
Name: rmT116609			Date: 05/11/2004


FULL PRODUCT VERSION :
java version "1.5.0-beta"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0-beta-b32c)
Java HotSpot(TM) Client VM (build 1.5.0-beta-b32c, mixed mode)


ADDITIONAL OS VERSION INFORMATION :
Linux freeway 2.4.21-4-686 #1 Sat Aug 2 23:27:25 EST 2003 i686 GNU/Linux


A DESCRIPTION OF THE PROBLEM :
java.util.Arrays.binarySearch() will throw an ArrayIndexOutOfBoundsException if the array
is large.  This is caused by overflow in the calculation:

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

The correct calculation uses unsigned shift:

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

There are similar problems in Collections, and TreeMap also includes the faulty calculation

           int mid = (lo + hi) / 2;

There may be others.


STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Run the included code example.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The code should print

index = 1099999999

ACTUAL -
The code printed

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1064671149
        at java.util.Arrays.binarySearch(Arrays.java:1509)
        at infinitum.tom.Search.main(Search.java:7)


ERROR MESSAGES/STACK TRACES THAT OCCUR :
$ /jdk/j2sdk1.5.0/bin/java -Xmx1200m -server Search
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1064671149
        at java.util.Arrays.binarySearch(Arrays.java:1509)
        at infinitum.tom.Search.main(Search.java:7)


REPRODUCIBILITY :
This bug can be reproduced rarely.

---------- BEGIN SOURCE ----------
class Search {
    public static void main (String[] args) {
        byte[] b = new byte[1100000000];
        b[b.length - 1] = 1;
        int index = java.util.Arrays.binarySearch(b, (byte)1);
        System.out.println("index = " + index);
    }
}
---------- END SOURCE ----------
(Incident Review ID: 261136) 
======================================================================

                                    

Comments
EVALUATION

Finally fixing for Mustang.
"Can't even compute average of two ints" is pretty embarrassing.
                                     
2006-04-18
EVALUATION

Should be fixed in the next release. Not for Tiger.
###@###.### 2004-05-11
                                     
2004-05-11



Hardware and Software, Engineered to Work Together