[Java]: Как извлечь ближайший меньший номер из отсортированного списка, когда запрошенный номер отсутствует в списке

Question

Я хочу получить ближайший меньший номер из отсортированного списка, когда запрашиваемого номера нет в списке. Например: список {10,14,55,97} и запрошенный номер 12, затем я хочу вернуть 10. Но код ниже возвращает 14. Этот код ищет в обоих направлениях в списке. Я хочу искать только в нижней части списка.

Я попробовал следующий код:

 public static int getClosestInteger(final List<Integer> listOfIntegers, final int requestedNumber) {

    int low = 0;
    int high = listOfIntegers.size() - 1;

    if (high < 0) {
        throw new IllegalArgumentException("The list cannot be empty");
    }

    while (low < high) {
        final int mid = (low + high) / 2;
        assert (mid < high);

        final int digit1 = Math.abs(listOfIntegers.get(mid) - requestedNumber);
        final int digit2 = Math.abs(listOfIntegers.get(mid + 1) - requestedNumber);
        if (digit2 <= digit1) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return listOfIntegers.get(high);
}

Есть предложения, что поменять?

Answer 1

Или ...

Вы можете добавить это число в список, найти его индекс, уменьшить на единицу и затем удалить его из списка: D

Answer 2

То, что вы делаете, является вариантом алгоритма двоичного поиска. Проверьте Процедура поиска самого левого элемента

В псевдокоде:

function binary_search_leftmost(A, n):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

Это позволит найти число элементов меньше T. И поскольку массивы начинаются с 0, все, что вам нужно сделать в конце, это

if A[L] == T:
    return A[L]
else:
    return A[L-1]

Это немного отличается от вашего алгоритма.