[알고리즘 실전] 파이썬으로 만드는 초고속 제곱근 계산기: 이분 검색(Binary Search)

 단순히 숫자를 1씩 더해가며 제곱근을 찾는 방식은 숫자가 커질수록 너무 오래 걸립니다. 오늘은 검색 범위를 매번 절반씩 뚝딱 줄여나가는 '이분 검색'의 마법을 알아보겠습니다.

1. 이분 검색의 핵심 원리

이분 검색은 정답이 있을 법한 범위를 정하고, 그 중간값을 확인해 범위를 좁혀가는 방식입니다.

• 중간값 확인: $low$와 $high$의 중간값($ans$)을 정합니다.

• 판단: $ans^2$이 우리가 찾는 값($x$)보다 크면? 정답은 중간보다 아래에 있습니다 ($high = ans$).

• 반복: 반대로 작으면? 정답은 중간보다 위에 있습니다 ($low = ans$).

  이렇게 하면 단 13번 정도의 계산만으로도 25의 제곱근에 아주 가깝게 다가갈 수 있습니다!

2. 파이썬 코드 핵심 분석

자막에 나온 코드의 주요 포인트는 다음과 같습니다.

Python

x = 25
epsilon = 0.01  # 오차 범위
low = 0
high = max(1.0, x)  # x가 1보다 작을 때를 대비한 설정
ans = (high + low) / 2.0

# 오차 범위 안에 들어올 때까지 무한 반복!
while abs(ans**2 - x) >= epsilon:
    if ans**2 < x:
        low = ans
    else:
        high = ans
    ans = (high + low) / 2.0  # 다시 중간값 잡기

• max(1.0, x)의 비밀: $x$가 0.25처럼 1보다 작은 수일 경우, 제곱근이 오히려 $x$보다 커집니다. 이를 처리하기 위해 검색 범위를 최소 1까지는 잡아주는 똑똑한 설계입니다.

• 다중 할당: 파이썬에서는 a, b = 1, 0처럼 여러 변수를 동시에 할당할 수 있어 코드가 아주 직관적이고 깔끔해집니다.

3. 다음 단계: 뉴턴 랍슨(Newton-Raphson) 방법

이분 검색도 훌륭하지만, 공학계에서 더 사랑받는 뉴턴 랍슨 방법도 있습니다. 다항식의 근을 훨씬 더 빠르고 우아하게 찾아내는 방법이죠. 알고리즘의 세계는 정말 끝이 없네요!

---

💡 오늘 요약

• 이분 검색: 검색 영역을 절반씩 줄여 효율성을 극대화합니다.

• 파이썬 활용: max() 함수와 다중 할당 문법으로 코드를 효율적으로 짭니다.

• 정확도: 오차 범위(epsilon)를 설정해 원하는 정밀도만큼 계산합니다.