이분탐색

이분 탐색(Binary Search)은 정렬된 배열에서 특정한 값을 찾는 알고리즘입니다. 배열의 중간값을 찾고, 그 중간값과 찾으려는 값의 크고 작음을 비교하여, 찾으려는 값이 중간값보다 크면 중간값의 오른쪽 부분 배열에서, 작으면 중간값의 왼쪽 부분 배열에서 다시 탐색하는 과정을 반복합니다. 이렇게 하면 매 단계마다 탐색해야 하는 배열의 크기가 반으로 줄어들기 때문에, 최악의 경우에도 O(log n)의 시간 복잡도로 탐색을 수행할 수 있습니다. 이분 탐색은 이진 검색(Binary Search)이라고도 불리며, 정렬된 배열에서 빠르게 탐색이 필요한 경우에 매우 유용합니다.

def base(n):
    if '.' in str(n):
        li = str(n).split('.')
        return float(li[0] + '.' + li[1][:2])
    else:
        return n


x, y = map(int, input().split())
# 이분 탐색
left, right = 0, 1000000000
answer = -1 # 미리 정해놓기

while left <= right:
    mid = (left + right) // 2
    new_x, new_y = x + mid, y + mid
    current_avg = base(new_y / new_x)
    if current_avg > base(y/x):
        answer = mid
        right = mid - 1
    else:
        left = mid + 1

print(answer)