Найти ближайший номер в массиве целых чисел - PullRequest
Новая
       57

Найти ближайший номер в массиве целых чисел

0 голосов
/ 03 ноября 2019

Учитывая массив отсортированных целых чисел, я хочу найти ближайшее значение к данному числу. Массив может содержать повторяющиеся значения и отрицательные числа. Пример: Input: arr [] = {-5, 2, 5, 6, 7, 8, 8, 9};Целевое число = 4 Выход: 5

Какой самый быстрый алгоритм? бинарный поиск? STL найти алгоритмы?

Спасибо за вашу помощь.

1 Ответ

3 голосов
/ 03 ноября 2019

В библиотеке std есть алгоритм, который почти точно выполняет то, что вы просите: std::lower_bound

Возвращает итератор, указывающий на первый элемент вдиапазон [первый, последний), который не меньше (то есть больше или равен) значению, или последний, если такой элемент не найден.

Вы можете использовать это, чтобы найти первый элемент, который являетсяравно или выше, чем ваша цель. Ответ - либо число, предшествующее ему.

Проверьте следующий пример: 

int find_closest(const vector<int>& A, const int a)
{
    if(A.size() <=0)
        throw std::invalid_argument("empty array");

    const auto lb = std::lower_bound(A.begin(), A.end(), a);
    int ans = lb!= A.end() ? *lb : A.back();
    if (lb != A.begin()) {
        auto prec = lb - 1;
        if (abs(ans - a) > abs(*prec - a))
            ans = *prec;
    }

    return ans;
}

Сложность этого подхода логарифмическая по размеру входной коллекцииlower_bound выполняет бинарный поиск. Это намного быстрее, чем простое решение, в котором вы будете перебирать всю коллекцию и проверять каждый элемент один за другим.

...