二分探索 配列中 より上の最小値
(library/search/binary_search/bi_gt_val.hpp)

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

二分探索 配列中 より上の最小値

できること

• 配列中の「xより上の最小値」を返す

計算量

• $O(logN)$

使い方

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

Verified with

• 二分探索 配列中 より上の最小値のテスト (tests/search.binary_search.bi_gt_val.test.cpp)

Code

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

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

Back to top page