Binary search to find the closest element

Question

I wrote a binary search to find the closest element to x in an array. How can show the correctness of the algorithm for any cases? Because it handles with floating points and variable length arrays, there are many cases.

import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Random;

public class BinarySearchWithAFuzzinessTest {
    /**
     * Returns the first occurrence, that fulfills the constraints.
     */
    public static int binaryContains(double[] list, double x, double delta) {
        if (list == null || list.length == 0) {
            throw new NoSuchElementException("provide at least one element");
        }
        int i = 0;
        int j = list.length / 2;
        int k = list.length - 1;
        int r = -1;
        if (x + delta < list[i]) {
            return r;
        }
        if (Math.abs(x - list[i]) <= delta) {
            r = i;
            delta = Math.nextAfter(Math.abs(x - list[i]), -1);
        }
        if (Math.abs(x - list[j]) <= delta) {
            r = j;
            delta = Math.nextAfter(Math.abs(x - list[j]), -1);
        }
        if (Math.abs(x - list[k]) <= delta) {
            r = k;
            delta = Math.nextAfter(Math.abs(x - list[k]), -1);
        }
        while (true) {
            System.out.println(i + " " + j + " " + k);
            if (x < list[j]) {
                k = j;
                j = (i + j) / 2;
                if (j == k) {
                    return r;
                }
                if (Math.abs(x - list[j]) <= delta) {
                    r = j;
                    delta = Math.nextAfter(Math.abs(x - list[j]), -1);
                } else if (Math.abs(x - list[k]) <= delta) {
                    r = k;
                    delta = Math.nextAfter(Math.abs(x - list[k]), -1);
                }
            } else if (x < list[k]) {
                i = j;
                j = (j + k) / 2;
                if (i == j) {
                    return r;
                }
                if (Math.abs(x - list[i]) <= delta) {
                    r = i;
                    delta = Math.nextAfter(Math.abs(x - list[i]), -1);
                } else if (Math.abs(x - list[j]) <= delta) {
                    r = j;
                    delta = Math.nextAfter(Math.abs(x - list[j]), -1);
                }
            } else {
                return r;
            }
        }
    }

    /**
     * Returns the first occurrence, that fulfills the constraints. This is for testing.
     */
    public static int linearContains(double[] list, double x, double delta) {
        for (int i = 0; i < list.length; i++) {
            if (Math.abs(x - list[i]) <= delta) {
                delta = Math.abs(x - list[i]);
                while (i + 1 < list.length && Math.abs(x - list[i + 1]) < delta) {
                    i++;
                    delta = Math.abs(x - list[i]);
                }
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Random r = new Random(1234);

        for (int i = 0; i < 100000; i++) {
            double[] a = new double[1 + r.nextInt(20)];
            double x = r.nextInt(20) - 10;
            double delta = r.nextDouble();
            for (int j = 0; j < a.length; j++) {
                if (r.nextBoolean()) {
                    a[j] = x + r.nextDouble() * 5 * delta;
                } else {
                    a[j] = x - r.nextDouble() * 5 * delta;
                }
            }
            Arrays.sort(a);

            int c1 = binaryContains(a, x, delta);
            int c2 = linearContains(a, x, delta);
            if (c1 != c2) {
                System.out.println("OOPS " + x + " " + delta);
                System.out.println(Arrays.toString(a) + " " + c1 + " " + c2);
                break;
            }
        }

        double[] a = {4, 4, 4};
        System.out.println(binaryContains(a, 4, 0));
        System.out.println(linearContains(a, 4, 0));
    }
}

Answer 1

Variable names

It's hard to read the code with one-letter variables. Sometimes it could be justified (like i and j as loop variables or names that were mentioned in a task); but usually you should name them array instead of a, binary instead of c1, result instead of r etc.

"Magic" numbers

Use named constants instead of hardcoded values.

static final int SEED = 1234;
static final int TEST_COUNT = 100000;

etc.

Different behavior

binaryContains throws NoSuchElementException when linearContains returns -1. If you're testing different algorithms - make sure you're testing the same behavior.

Changing arguments is bad

What if you'll need an initial value of delta after you've changed it? Yes, sometimes it's OK and even needed, but not here. Leave delta as it was and add a new variable - maybe "closest" or something like to store current closest value.

Math.nextAfter is a delicate tool for floating point manipulation

You don't need it in common math, just compare using <, not <=.

Unnecessary loop in linearContains

The inner loop goes over the array one by one, as well as the outer loop. You can refactor it into a single loop.

Better algorithm

First, do a binary search until \$a[i]≤x≤a[i+1]\$. Next, check if distance from the closest is less than delta, checking it during the search is useless.

Your question

Formal verification is hard, but usually unit tests covering all possible paths of execution and known former bugs are good enough for practical use.