二分探索 配列中 以下の最大値
(library/search/binary_search/bi_le_val.hpp)

• View this file on GitHub
• Last update: 2026-01-15 10:11:56+09:00
• Include: #include "library/search/binary_search/bi_le_val.hpp"

二分探索 配列中 以下の最大値

できること

• 配列中の「x以下の最大値」を返す

計算量

• $O(logN)$

使い方

sort(A.begin(), A.end());
int v = bi_le_val(A, x);
int v = bi_le_val(st, x);
if (v == -INF) {
    // 値が存在しなかった
}

Verified with

• 二分探索 配列中 以下の最大値のテスト (tests/search.binary_search.bi_le_val.test.cpp)

Code

#pragma once
template <typename T> T bi_le_val(vector<T> &v, const T &x) {
    auto it = upper_bound(v.begin(), v.end(), x);
    return (it == v.begin() ? -INF : *--it);
}
template <typename T> T bi_le_val(const set<T> &st, const T &x) {
    auto it = st.upper_bound(x);
    return (it == st.begin() ? -INF : *--it);
}

#line 2 "library/search/binary_search/bi_le_val.hpp"
template <typename T> T bi_le_val(vector<T> &v, const T &x) {
    auto it = upper_bound(v.begin(), v.end(), x);
    return (it == v.begin() ? -INF : *--it);
}
template <typename T> T bi_le_val(const set<T> &st, const T &x) {
    auto it = st.upper_bound(x);
    return (it == st.begin() ? -INF : *--it);
}

Back to top page