Как лучше решить задачу на поиск ближайшего числа?

Question

[Алексей Струков]

Приветствую. Вот суть задачи:
Есть функция findClosest, которая принимает неотсортированный массив чисел, число которое надо найти и функцию-компаратор. Компаратор должен определять одно из 4 возможных типов поведения для findClosest:

Если число отсутствует в массиве, то:

• находить ближайшее меньшее число
  
• находить ближайшее большее число
  
• находить ближайшее число, но если оно равноудалено от значений массива, брать то, что меньше
  
• находить ближайшее число, но если оно равноудалено от значений массива, брать то, что больше
  

Если в массиве нет данных подходящих по условию - вернуть false:

Какие есть изящные решения?

Comments

[Dmitri Sinitsa]

На ум приходит бинарное дерево (bst). Надо будет проверить догадку.

[Алексей Струков]

Dmitri Sinitsa: придется сортировать предварительно)

[Dmitri Sinitsa]

Алексей Струков: для построения дерева сортировка не нужна

[Алексей Струков]

Dmitri Sinitsa: а как тогда будет происходить поиск по нему?

[Dmitri Sinitsa]

Алексей Струков: как в обычном бинарном дереве: слева от вершины - числа меньше, справа - больше. В зависимости от компаратора двигаться по левой или правой стороне. Но это набросок идеи - возможно я не прав.

Кстати, поиск самого числа не обязательно делать в дереве. Разумнее использовать словарь (доступ за O(1)). А дерево заюзать для поиска ближайшего меньшего/большего.

[Алексей Струков]

Dmitri Sinitsa: поэтому я и говорю, что массив придется сортировать, чтобы слева числа были меньше, а справа - больше. Словарь здесь не подойдет, так как искомого числа в нем может не оказаться и тогда понадобится вернуть другое число определенное компаратором.

Answer 1

[Алексей Струков]

Вот решение, которое я нашел (если кому понадобится в будущем):

/**
     * @param {Array} settings.arr
     * @param {Number} settings.valueToFind
     * @param {Function} settings.comparator
     *
     * @returns {Number|undefined}
     */
    function findClosest(settings) {

      var lo                 = -Infinity,
            hi                 = Infinity,
            arr                = settings.arr,
            valueToFind = settings.valueToFind,
            comparator  = settings.comparator,
            result;

        for (var i = 0; i < arr.length; i++) {

            if (arr[i] <= valueToFind && arr[i] >= lo) {
                lo = arr[i];
                continue;
            }

            if (arr[i] >= valueToFind && arr[i] <= hi) {
                hi = arr[i];
            }
        }

        result = comparator(lo, hi, valueToFind);

        return isFinite(result) ? result : undefined; // or false
    }

Вот так выглядит объект settings c четырьмя возможными компараторами:

var comparator1 = function(lo, hi, valueToFind) {
        return lo; // or hi
};

var comparator2 = function(lo, hi, valueToFind) {
        var result = lo; // or hi

        switch (true) {
            case valueToFind - lo < hi - valueToFind:
                result = lo;
                break;
            case valueToFind - lo > hi - valueToFind:
                result = hi;
                break;
        }

        return result;
};
 
var settings = {
        arr: [1, 5, 10, 8, 5, 13],
        valueToFind: 7,
        comparator: comparator2
};

И сам вызов функции:

alert(findClosest(settings));

PS:
Вместо false, в случае когда результат не определен, я решил возвращать undefined, так как это значение ближе по семантике.

Answer 2

[Nurba Nurba]

сортировать массив каким нибудь алгоритмом . после находить числа бинарным поиском)

Comments

[Алексей Струков]

Это один из вариантов, но так как сортировка это деструктивный метод, то придется предварительно копировать массив, а еще нужен компаратор для самой сортировки, чтобы она корректно обрабатывала цифры. В итоге это уже не будет изящно)

[Nurba Nurba]

я что то не втыкаю в задаче. требование никаких манипуляций нельзя делать с массивом ?

[Алексей Струков]

Nurba Nurba: это не желательно. Иммутабельность, все дела)

Answer 3

[tomatho]

Для третьего и четвёртого варианта невозможно из компаратора узнать был ли уже на таком же расстоянии.
Выход который я вижу: "сместить" в пользу "низа", но это возможно только с определённой точностью.
Второй вариант: можно сделать если передавать в компаратор три значения: текущее, лучшее сейчас, и то что ищем.

Далее код для a, b - текущее, то что ищем соответственно.
Код не проверял.

function c1(a, b) {
  return (a <= b ? b - a : Number.MAX_VALUE );
}
function c2(a, b) {
  return (a >= b ? a - b : Number.MAX_VALUE );
}
function c3(a, b) {
  if (a <= b && b - a < Math.abs(b)*(1e-7))
    return 0;
  return Math.abs(a - b + Math.abs(b)*(1e-7));
}
function c4(a, b) {
  if (a >= b && a - b < Math.abs(b)*(1e-7))
    return 0;
  return Math.abs(a - b - Math.abs(b)*(1e-7));
}

Comments

[Алексей Струков]

Без описания функции findClosest непонятно почему возвращается (b - a) например в первом компараторе. Ну и не обязательно передавать только два параметра. Можно хоть десять, если они помогут решить задачу.
PS: Задачу уже решил сам. Если не увижу более лаконичного решения, то выложу свой вариант.

[tomatho]

Алексей Струков: Сказано же, что findClosest уже есть.

Есть функция findClosest, которая принимает неотсортированный массив чисел, число которое надо найти и функцию-компаратор. Компаратор должен определять одно из 4 возможных типов поведения для findClosest:

Ну решил, так решил. Молодец.