JDK-5045582 : (coll) binarySearch() fails for size larger than 1<<30
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util:collections
  • Affected Version: 5.0,6
  • Priority: P2
  • Status: Closed
  • Resolution: Fixed
  • OS: generic,linux
  • CPU: generic,x86
  • Submitted: 2004-05-11
  • Updated: 2012-10-08
  • Resolved: 2006-04-29
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 6
6 b83Fixed
Related Reports
Duplicate :  
Relates :  
Relates :  
Relates :  
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