Bisect
(algo/search/bisect.hpp)

• View this file on GitHub
• Last update: 2026-07-07 21:49:48+09:00
• Include: #include "algo/search/bisect.hpp"

Overview

Binary search helpers for monotone predicates. The integer functions use explicit ok and ng sentinels, so they work for both increasing and decreasing search directions.

Functions

Function	Description	Complexity
long long first_true(long long ng, long long ok, F pred)	Given pred(ng) == false and pred(ok) == true, returns the boundary ok.	$O(\log	ok - ng	)$
long long last_true(long long ok, long long ng, F pred)	Given pred(ok) == true and pred(ng) == false, returns the boundary ok.	$O(\log	ok - ng	)$
double real_first_true(double ng, double ok, F pred, int iterations = 80)	Floating-point version of first_true with a fixed iteration count.	$O(\text{iterations})$

Example

#include "algo/search/bisect.hpp"
#include <iostream>

int main() {
    long long n = 100;
    long long x = m1une::algo::first_true(0, n + 1, [&](long long v) {
        return v * v >= n;
    });
    std::cout << x << "\n";
}

Required by

• Algorithms All (algo/all.hpp)
• Search Algorithms All (algo/search/all.hpp)

Verified with

• verify/algo/search/bisect.test.cpp

Code

#ifndef M1UNE_ALGO_SEARCH_BISECT_HPP
#define M1UNE_ALGO_SEARCH_BISECT_HPP 1

#include <numeric>

namespace m1une {
namespace algo {

template <typename F>
long long first_true(long long ng, long long ok, F pred) {
    auto distance = [](long long a, long long b) {
        return a > b ? static_cast<__int128_t>(a) - b : static_cast<__int128_t>(b) - a;
    };
    while (distance(ng, ok) > 1) {
        long long mid = std::midpoint(ng, ok);
        if (pred(mid)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}

template <typename F>
long long last_true(long long ok, long long ng, F pred) {
    auto distance = [](long long a, long long b) {
        return a > b ? static_cast<__int128_t>(a) - b : static_cast<__int128_t>(b) - a;
    };
    while (distance(ok, ng) > 1) {
        long long mid = std::midpoint(ok, ng);
        if (pred(mid)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}

template <typename F>
double real_first_true(double ng, double ok, F pred, int iterations = 80) {
    for (int i = 0; i < iterations; ++i) {
        double mid = (ng + ok) / 2.0;
        if (pred(mid)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}

}  // namespace algo
}  // namespace m1une

#endif  // M1UNE_ALGO_SEARCH_BISECT_HPP

#line 1 "algo/search/bisect.hpp"



#include <numeric>

namespace m1une {
namespace algo {

template <typename F>
long long first_true(long long ng, long long ok, F pred) {
    auto distance = [](long long a, long long b) {
        return a > b ? static_cast<__int128_t>(a) - b : static_cast<__int128_t>(b) - a;
    };
    while (distance(ng, ok) > 1) {
        long long mid = std::midpoint(ng, ok);
        if (pred(mid)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}

template <typename F>
long long last_true(long long ok, long long ng, F pred) {
    auto distance = [](long long a, long long b) {
        return a > b ? static_cast<__int128_t>(a) - b : static_cast<__int128_t>(b) - a;
    };
    while (distance(ok, ng) > 1) {
        long long mid = std::midpoint(ok, ng);
        if (pred(mid)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}

template <typename F>
double real_first_true(double ng, double ok, F pred, int iterations = 80) {
    for (int i = 0; i < iterations; ++i) {
        double mid = (ng + ok) / 2.0;
        if (pred(mid)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}

}  // namespace algo
}  // namespace m1une

Back to top page