import java.util.Arrays;
/**
* Static methods for doing useful math
*
* @author : $Author: brian $
* @version : $Revision: 1.1 $
*
*
* The Monterey Bay Aquarium Research Institute (MBARI) provides this
* documentation and code "as is", with no warranty, express or
* implied, of its quality or consistency. It is provided without support and
* without obligation on the part of MBARI to assist in its use, correction,
* modification, or enhancement. This information should not be published or
* distributed to third parties without specific written permission from
* MBARI.
*
* Copyright 2002 MBARI.
* MBARI Proprietary Information. All rights reserved.
*
*/
public class Util{
/**
* Searches the specified array of doubles for the specified value using
* the binary search algorithm. The array must be sorted
* (as by the sort method, above) prior to making this call. If
* it is not sorted, the results are undefined. If the array contains
* multiple elements with the specified value, there is no guarantee which
* one will be found. The array can be sorted from low values to high or
* from high values to low.
*
* @param a the array to be searched.
* @param key the value to be searched for.
* @return index of the search key, if it is contained in the list;
* otherwise, (-(insertion point) - 1). The
* insertion point is defined as the point at which the
* key would be inserted into the list: the index of the first
* element greater than the key, or list.size(), if all
* elements in the list are less than the specified key. Note
* that this guarantees that the return value will be >= 0 if
* and only if the key is found.
*/
public static int binarySearch(double[] a, double key) {
int index = -1;
if (a[0] < a[1]) {
index = Arrays.binarySearch(a, key);
}
else {
index = binarySearch(a, key, 0, a.length - 1);
}
return index;
}
private static int binarySearch(double[] a, double key, int low, int high) {
while (low <= high) {
int mid = (low + high) / 2;
double 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 {
long midBits = Double.doubleToLongBits(midVal);
long keyBits = Double.doubleToLongBits(key);
cmp = (midBits == keyBits ? 0 : (midBits < keyBits ? -1 : 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.
}
}