二分探索の練習問題

A - 二分探索の練習問題

O(logN)

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    l = -1
    r = N
    while abs(r-l)>1:
        mid = (l + r) // 2
        if A[mid] >= K:
            r = mid
        else:
            l = mid

    if r==N:
        print(-1)
    else:
        print(r)


# エントリポイント
if __name__ == '__main__':
    main()

C - Buy an Integer

O(logN)

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    A, B, X = list(map(int, input().split()))

    ok = 0
    ng = 10**9 + 1

    while abs(ok-ng) > 1:
        mid = (ok + ng) // 2
        d = len(str(mid))
        price = mid * A + B * d
        if X >= price:
            ok = mid
        else:
            ng = mid
    print(ok)

# エントリポイント
if __name__ == '__main__':
    main()

B - 花束

O(logN)

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    R, B = list(map(int, input().split()))
    x, y = list(map(int, input().split()))

    def check(X):
        r = R - X
        b = B - X
        if r<0 or b<0:
            return False
        num = r // (x-1) + b // (y-1)
        return (num>=X)

    ok = 0
    ng = 10**18 + 1

    while abs(ok - ng) > 1:
        mid = (ok+ng) // 2
        if check(mid):
            ok = mid
        else:
            ng=mid
    
    print(ok)

        
# エントリポイント
if __name__ == '__main__':
    main()