Find the k-th largest integer using oracle (tools/kth_largest_by_oracle.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2025-12-07 12:31:51+09:00
Include: #include "tools/kth_largest_by_oracle.hpp"

template <typename F>
requires std::regular_invocable<F, long long>
      && std::assignable_from<long long&, std::invoke_result_t<F, long long>>
long long kth_largest_by_oracle(long long k, F f, long long l, long long r);

Suppose that we have a multiset $S$ of integers, and we cannot directly examine $S$, but we can get $f(x)$, the number of elements in $S$ that are greater than or equal to $x$. Given $k$, $f$ and $[l, r]$, the domain of definition of $f$, it returns the $k$-th largest integer in $S$.

Constraints

$1 \leq k \leq f(l)$
$l \leq r$
For any $i$ and $j$ such that $l \leq i < j \leq r$, $f(i) \geq f(j)$

Time Complexity

$O(\log (r - l) \cdot T)$ where $T$ is the time required to get $f(x)$

License

Author

anqooqie

Depends on

tools/detail/kth_largest_by_oracle.hpp

Verified with

tests/kth_largest_by_oracle.test.cpp

Code

#ifndef TOOLS_KTH_LARGEST_BY_ORACLE_HPP
#define TOOLS_KTH_LARGEST_BY_ORACLE_HPP

#include <utility>
#include "tools/detail/kth_largest_by_oracle.hpp"

namespace tools {
  template <typename... Args>
  auto kth_largest_by_oracle(Args&&... args) {
    return tools::detail::kth_largest_by_oracle::impl<true>(std::forward<Args>(args)...);
  }
}

#endif

#line 1 "tools/kth_largest_by_oracle.hpp"



#include <utility>
#line 1 "tools/detail/kth_largest_by_oracle.hpp"



#include <cassert>
#include <cmath>
#include <concepts>
#include <numeric>
#include <type_traits>
#include <tuple>
#line 11 "tools/detail/kth_largest_by_oracle.hpp"

namespace tools {
  namespace detail {
    namespace kth_largest_by_oracle {
      template <bool largest, typename F>
      requires std::regular_invocable<F, long long>
            && std::assignable_from<long long&, std::invoke_result_t<F, long long>>
      long long impl(const long long k, const F& f, const long long l, const long long r) {
        assert(1 <= k && k <= f(largest ? l : r));
        assert(l <= r);

        long long ok, ng;
        std::tie(ok, ng) = largest ? std::make_pair(l - 1, r + 1) : std::make_pair(r + 1, l - 1);
        while (std::abs(ng - ok) > 1) {
          const auto mid = std::midpoint(ok, ng);
          (std::cmp_greater_equal(f(mid), k) ? ok : ng) = mid;
        }
        return ok;
      }
    }
  }
}


#line 6 "tools/kth_largest_by_oracle.hpp"

namespace tools {
  template <typename... Args>
  auto kth_largest_by_oracle(Args&&... args) {
    return tools::detail::kth_largest_by_oracle::impl<true>(std::forward<Args>(args)...);
  }
}