강의로 돌아가기
Lim Sung Hoo

이진탐색 질문있습니다.

코드 실습 돌려보니 마지막 원소 15를 찾을 때는 에러가 발생하던데, 시스템 테스트 코드에서는 이게 발견되지 않네요 ㅎ,, 어떤점이 문제인지 알수있을가요?

def solution(L, x):
    m_index = (0 + (len(L) - 1)) // 2
    s_index = 0
    e_index = len(L) - 1

    while L[s_index] <= L[e_index] and ((L[s_index] or L[e_index]) != L[m_index]):
        if L[m_index] == x:
            return m_index

        elif L[m_index] < x:
            s_index = m_index
            m_index = (s_index + e_index) // 2

        else:
            e_index = m_index
            m_index = (s_index + e_index) // 2

    return -1
L = [2, 3, 5, 6, 9, 11, 15]

print(solution(L, 15))
1 개의 답변
이시윤

기본적인 아이디어에 대해서는 비슷하게 구현이 된 것 같습니다만, 몇 가지 올바르지 않은 점이 있습니다.

(1) 처음에는 m_index = (0 + (len(L) - 1)) // 2 로 하고 있는데, 이것은 (0 은 더하나 마나이니까) 그냥 (len(L) - 1) // 2 와 같습니다. 하지만, 왜 여기에서는 1을 빼는 것인가요? 뒤의 (순환문 내의) m_index = (s_index + e_index) // 2 와 다르게 한 이유가 있는지요?

(2) while 의 조건 (and 로 이어진) 중 두번째 것, 즉 (L[s_index] or L[e_index]) != L[m_index] 은 아마도 L[s_index] 또는 L[e_index] 중 어느 한 쪽이라도 L[m_index] 와 같은 경우를 뜻하려 한 것 같은데, Python 에서 위 문장은 그렇게 동작하지 않습니다. (이것은 Python 의 조금 어려운 내용이므로 여기에서 자세하게 언급하지는 않겠습니다.) 만약 좌변의 둘 중 하나가 우변과 같은 경우를 표현하고 싶었다면, `L[s_index] == L[m_index] or L[e_index] == L[m_index]' 와 같이 표현해야 합니다. 불구하고, while 조건에서 이것을 검사하는 것은 이진 탐색에서 권하고 싶은 방식은 아닙니다.

(3) while 의 조건 중 첫 번째 것, 즉 L[s_index] <= L[e_index] 에서는 배열의 두 원소 (각각 s_indexe_index 가 가리키고 있는) 의 크기를 비교하고 있습니다만, 이진탐색 알고리즘의 원래 버전에서는 인덱스 자체를 비교하여 더 이상 검사해야 할 배열 (의 부분) 이 남아 있지 않은지를 검사하도록 되어 있습니다. (왜일까요? 한번 생각해 보기 바랍니다.)

마지막으로, 위 코드는 첫번째 원소 (2) 또는 마지막 원소 (15) 를 탐색 시도할 때 올바른 결과를 내지 못합니다. (x 에 2 가 주어진 경우와 15 가 주어진 경우에 어떻게 동작하는지를 종이와 연필로, 또한 print() 문을 코드 사이사이에 넣어서, 살펴보세요.) 아래와 같은 코드를 이용해서 확인해 보는 것도 괜찮은 방법이 될 듯합니다,.

L = [2, 3, 5, 6, 9, 11, 15]

for x in L:
    sol = solution(L, x)
    print(sol)

주의할 점은, 이 코드에 의한 테스트를 모두 통과한다고 해서 이진 탐색 알고리즘이 올바르게 구현되었구나, 라고 생각할 수 있는 것은 아니라는 점입니다. (그렇다면 어떻게 테스트해야 올바른 걸까요? 생각해 보기 바랍니다. 특히, Python 강좌나 참고 서적에서 단위 테스트 에 관련한 부분이 있다면 참고하는 것이 좋겠습니다.

  • Lim Sung Hoo
    감사합니다. 강사님 덕분에 제대로 생각하는 법을 배웠습니다 :)) Lim Sung Hoo 2018.08.13 11:12
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.