Бинарный поиск для поиска ближайшего элемента

Я написал двоичный поиск, чтобы найти ближайший к x элемент в массиве. Как можно показать правильность алгоритма для любых случаев? Поскольку он обрабатывает массивы с плавающей запятой и переменной длины, есть много случаев.

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));
    }
}

Имена переменных

Код с однобуквенными переменными сложно читать. Иногда это могло быть оправдано (например, i и j как переменные цикла или имена, упомянутые в задаче); но обычно вы должны назвать их array вместо a, binary вместо c1, result вместо r и т.п.

«Волшебные» числа

Используйте именованные константы вместо жестко заданных значений.

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

и т.п.

Другое поведение

binaryContains бросает NoSuchElementException когда linearContains возвращает -1. Если вы тестируете разные алгоритмы — убедитесь, что вы тестируете одно и то же поведение.

Менять аргументы — плохо

Что, если вам понадобится начальное значение дельты после того, как вы его изменили? Да, иногда это нормально и даже нужно, но не здесь. Оставьте дельту как есть и добавьте новую переменную — возможно «closest«или что-то вроде сохранения текущего ближайшего значения.

Math.nextAfter это тонкий инструмент для работы с числами с плавающей запятой

Вам это не нужно в обычной математике, просто сравните, используя <, нет <=.

Ненужная петля в linearContains

Внутренний цикл проходит по массиву один за другим, а также внешний цикл. Вы можете реорганизовать его в один цикл.

Лучший алгоритм

Сначала выполните двоичный поиск, пока $ a[i]≤x≤a[i+1] $. Затем проверьте, не меньше ли расстояние от ближайшего delta, проверять при поиске бесполезно.

Ваш вопрос

Формальная проверка сложно, но обычно модульные тесты охват всех возможных путей выполнения и известных ранее ошибок достаточно хорош для практического использования.