[Python] Parametric Search

▶ Parametric Search 매개변수 탐색 

 

binary search를 이용한 기법 중 하나 

원하는 값을 탐색하는 알고리즘 

최대, 최소를 찾는 문제를 O, X로 바꿔서 접근하는 방식이다. 

시간복잡도는 O(logN)

 

# parametric search 
# 차 있는 배터리 갯수 찾기 

battery ="###_________"

def parametric(st, ed):
    Max = - 1
    while 1:
        mid = ( st + ed ) // 2
        if battery[mid] == '#':
            Max = mid
            st = mid + 1
        elif battery[mid] == '_':
            ed = mid - 1
        if st > ed :
            break
    return Max + 1

ans = parametric(0,9)
print(ans)