Как найти ближайшее меньшее число в массиве?
Ответы 1
Как проще всего найти ближайшее меньшее число в массиве, желательно от
<algorithm>?
Для этого можно использовать уже существующий std::lower_bound (или std::ranges::lower_bound, начиная с C++20). Проверьте пример кода, приведенный на указанных страницах.
Например, вы можете написать функцию следующим образом. Я оставляю вам обработку ошибок, а также доработку крайних случаев.
#include <algorithm> // std::ranges::lower_bound
constexpr auto find_equal_or_closest(std::vector<int> const& numbers, const int query)
{
// invalid query/ not able to find cases!
// you could also restructure to return std::cend(numbers) from function.
if (numbers.empty()
/* || !std::ranges::is_sorted(numbers) */ // optional check
|| query < *std::cbegin(numbers)
)
return -1;
auto it = std::ranges::lower_bound(numbers, query);
return (it != std::cend(numbers) && *it == query) ? *it : *std::prev(it);
}
Нижняя граница возвращает первую, которая не меньше заданного значения.
Скорректировано на основе вашего обновленного ответа... Мне нравится этот трюк... все еще используйте low_bound, но потом настройте итератор....
отказываюсь от своего закрытого голосования, потому что это намного лучше, чем другой ответ, ИМХО
@UpAndAdam Как уже упоминалось, это не идеальное решение, а скорее направление к реальной проблеме ОП. ОП должен думать/обрабатывать все потоки в данном случае в соответствии со своими крайними случаями.
Извините, забыл удалить свой первый ответ. Должен сказать, что мне это нравится, это так просто, но я никогда раньше об этом не думал. Для меня это теперь идеальное решение. И бонусные баллы за живую демонстрацию с Godbolt... Мне нужно начать делать это в своих ответах. Вы действительно отличный пользователь с высокой репутацией, я отдаю вам должное. В последнее время у меня было так много неприятных событий с людьми с высокой репутацией, что это действительно освежает. Образцовое движение туда-сюда. Спасибо, что показали мне, как лучше самому отвечать на вопросы.
когда в массиве нет меньшего числа, вы возвращаете итератор первому элементу, в этом случае я бы предпочел ожидать end
ооо, это хороший угловой случай. @463035818_is_not_an_ai не подумал об этом... забавные угловые случаи.
Поскольку вы описываете отсортированный массив (который, предположительно, при тестировании будет намного больше), какой-то двоичный поиск, вероятно, будет «самым простым» способом достижения этой цели, где самым простым является «наименьшая временная сложность». Не уверен, что что-либо в
<algorithm>покрывает это.