cp_library/alg/divcon/fbisect_fn.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00

Verified with

• test/atcoder/abc/abc151_f_fbisect_left.test.py

Code

import cp_library.alg.divcon.__header__

def fbisect_left(key, hi, x = True, lo = 0.0, tol=1e-9):
    while hi - lo > tol:            
        mid = (lo + hi) / 2
        if key(mid) >= x:
            hi = mid
        else:
            lo = mid
            
    return lo

def fbisect_right(key, hi, x=False, lo=0.0, tol=1e-9):
    while hi - lo > tol:
        mid = (lo + hi) / 2
        if key(mid) > x:
            hi = mid
        else:
            lo = mid
    return hi

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''

def fbisect_left(key, hi, x = True, lo = 0.0, tol=1e-9):
    while hi - lo > tol:            
        mid = (lo + hi) / 2
        if key(mid) >= x:
            hi = mid
        else:
            lo = mid
            
    return lo

def fbisect_right(key, hi, x=False, lo=0.0, tol=1e-9):
    while hi - lo > tol:
        mid = (lo + hi) / 2
        if key(mid) > x:
            hi = mid
        else:
            lo = mid
    return hi

Back to top page