Name: bsC130419 Date: 06/18/2001


java version "1.4.0-beta"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.0-beta-b65)
Java HotSpot(TM) Client VM (build 1.4.0-beta-b65, mixed mode)

Arrays.binarySearch(float[])'s implementation makes use of Float.floatToIntBits
(float), which collapse all NaN values into a single canonical one.
Consequently, when searching a specific NaN number, Arrays.binarySearch(float
[]) find a random NaN number. The problem is shown by the following test case:




import java.util.Arrays;

public class Test
{
    private static void print(float value)
    {
        System.out.print(value);
        System.out.print(" (");
        System.out.print(Integer.toHexString(Float.floatToRawIntBits(value)));
        System.out.print(')');
    }

    public static void main(String[] args)
    {
        // Note: this array fully respect the "Float.compare"
        // ordering: NaN values are last.
        float[] data =
        {
            0.4f,
            8.7f,
            9.3f,
            Float.intBitsToFloat(0x7fc00001), // NaN
            Float.intBitsToFloat(0x7fc00002), // NaN
            Float.intBitsToFloat(0x7fc00003), // NaN
            Float.intBitsToFloat(0x7fc00004) // NaN
        };
        for (int i=0; i<data.length; i++)
        {
            System.out.print("search ");
            print(data[i]);
            final int index = Arrays.binarySearch(data, data[i]);
            System.out.print(", found ");
            print(data[index]);
            System.out.println();
        }
    }
}

--------------------------
% java Test
search 0.4 (3ecccccd), found 0.4 (3ecccccd)
search 8.7 (410b3333), found 8.7 (410b3333)
search 9.3 (4114cccd), found 9.3 (4114cccd)
search NaN (7fc00001), found NaN (7fc00001)
search NaN (7fc00002), found NaN (7fc00001)
search NaN (7fc00003), found NaN (7fc00001)
search NaN (7fc00004), found NaN (7fc00001)
%
--------------------------


The test case show that Arrays.binarySearch(float[]) do not find the NaN value
we requested. It may be possible to fix the problem with minimal risk. There is
the Arrays.binarySearch(float[]) source code:



private static int binarySearch(float[] a, float key, int low,int high) {
    while (low <= high) {
        int mid =(low + high)/2;
        float midVal = a[mid];

        int cmp;
        if (midVal < key) {
            cmp = -1; // Neither val is NaN, thisVal is smaller
        } else if (midVal > key) {
            cmp = 1; // Neither val is NaN, thisVal is larger
        } else {
            int midBits = Float.floatToIntBits(midVal);
            int keyBits = Float.floatToIntBits(key);
            cmp = (midBits == keyBits ? 0 : // Values are equal
                   (midBits < keyBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
                    1)); // (0.0, -0.0) or (NaN, !NaN)
        }

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1); // key not found.
}





  Suggested fix: Replace the two Float.floatToIntBits(float) calls by
Float.floatToRawIntBits(float). In order to preserve backward compatibility
with existing programs (since current behavior never return an insertion point
between two NaN values), add a new line before the last line:



if (Float.isNaN(key) && low<a.length) return low; // For backward compatibility
return -(low+1);



The suggested fix will make absolutely no difference when using
Arrays.binarySearch(float[]) with only real numbers, infinities and the
canonical Float.NaN value, which cover most cases. If the array contains a set
of different NaN values, then there are two possible cases:


Case 1) NaN values are sorted in increasing order (as returned by
Float.floatToRawIntBits(float)). In this case, Arrays.binarySearch(float[])
will work as expected. However, because of last lines change,
Arrays.binarySearch(float[]) will returns a positive index even if no exact
match is found for a NaN value. This is necessary for backward compatibility.

Case 2) NaN values are not sorted in increasing order, because legacy code was
not multi-NaN aware. In this case, Arrays.binarySearch(float[]) will returns a
random NaN number, which is quite similar to the current behavior. The only
difference is that it may not be the same random NaN than before. In both case,
the specification is not violated and compatibility with existing code should
not be broken.
(Review ID: 126773)
======================================================================