Get Smallest Difference between Adjacent Array Elements in a Sorted List

Question

Hi, I have a sorted list of ratios, and I need to find a "bin size" that is small enough so that none of them overlap. To put it shortly, I need to do what the title says. If you want a little background, read on.

I am working on a graphical experiment that deals with ratios and the ability of the eye to distinguish between these ratios quickly. So when we are forming these experiments, we use flashes of dots with various ratios chosen from dot bins. A bin is just a range of possible ratios with the mentioned array elements in the center. All dot bins need to be the same size. This means that we need to find the elements in the array that are nearest each other. Keep in mind that the array is sorted.

Can anyone think of a quick cool way to do this? I have never been particularly algorithmically inclined, so right now I am just running through the array backwards and subtracting the next element from the current one and checking that against a sum. Thanks

private double findNumerostyBinRangeConstant(double[] ratios) {
        int minI = 0;
        double min = 0;
        for (int i = ratios.length -1; i > 0; i--) {
            if (ratios[i] - ratios[i-1] > min) {
                min = ratios[i] - ratios[i-1];              
                minI = i;
            }
        }
        return Math.sqrt(ratios[minI]/ratios[minI - 1]); //Essentiall a geometric mean. Doesn't really matter.
    }

Answer 1

Only change: flipped the array search to go in increasing direction -- many architectures prefer going in positive direction. (Some don't.) Haven't verified that I didn't introduce an off-by-one error. (Sorry.)

private double findNumerostyBinRangeConstant(double[] ratios) {
        int minI = 0;
        double min = Double.MAX_VALUE;
        for (int i = 0; i <= ratios.length-1; i++) {
            if (ratios[i+1] - ratios[i] < min) {
                min = ratios[i+1] - ratios[i];              
                minI = i;
            }
        }
        return Math.sqrt(ratios[minI+1]/ratios[minI]);
    }

Answer 2

Forward moving functions, fixed some logic issues that you had. Since you are looking for the minimum double, your initial comparison variable should start at the max. Removed the comparison by subtraction because you weren't using it later, replaced it with the division. Note: Haven't tested the fringe cases, including zeros and negatives.

private double findNumerostyBinRangeConstant(double[] ratios) {
    double result = Double.MAX_VALUE;
    for (int i = 0; i<ratios.length-1; i++) {
        if (ratios[i+1]/ratios[i] < result){
            result = ratios[i+1]/ratios[i];
        }
    }
    return Math.sqrt(result);
}