Name: rmT116609 Date: 03/27/2003


FULL PRODUCT VERSION :
ava version "1.4.1_02"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.1_02-b06)
Java HotSpot(TM) Client VM (build 1.4.1_02-b06, mixed mode)


FULL OS VERSION :
Linux localhost.localdomain 2.4.18-27.8.0 #1 Fri Mar 14 06:45:49 EST 2003 i686 i686 i386 GNU/Linux


A DESCRIPTION OF THE PROBLEM :
The binary search match does not work properly of some input. When the key is not present in the array, but the key is bigger than first element in array and smaller than the last element in the array. According to the API it shall return the index of smallest number that is bigger than key. But it returns -6586 is one of the test cases. See test case and source code attached below.

This bug also presents in Windows XP version of JDK1.4.1_02

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Just compile the attached code: JDKArraysBinarySearchBug.java
and then run it use java JDKArrayBinarySearchBug


REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
http://judge.comp.nus.edu.sg:8000/cs1102/bugs/JDKArraysBinarySearchBug.java
---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
    /**
     * Return the index of smallest number that is not smaller than key.
     */
    public static int binarySearch(int[] data, int key) {
        if (key <= data[0]) return 0;
        int high = data.length - 1;
        if (key > data[high]) return data.length;
        int low = 0;

        //invariant data[low] < key <= data[high]
        while (low+1 < high) {
            int mid = (low + high) / 2;
            if (key > data[mid]) low = mid;
            else if (key < data[mid]) high = mid;
            else return mid;
        }
        return high;
    }
(Review ID: 182953)
======================================================================