이진 검색

이진 검색은 정렬된 리스트에서 원하는 항목을 찾기에 효율적인 알고리즘입니다. 이 검색법은 후보 범위가 한 항목으로 좁아질 때까지 찾고자 하는 항목을 포함하고 있는 리스트를 반으로 나누는 과정을 계속 반복합니다. 이전에 추측 게임에서 이진 검색을 사용해 보았습니다.

이진 검색을 가장 많이 사용하는 경우는 배열에서 어떤 항목을 찾아야 할 때입니다. 예를 들어 티코(Tycho)-2 항성 목록은 우리 은하계에서 가장 밝은 별 2,539,913개의 정보를 담고 있습니다. 별의 이름을 검색하여 항성 목록에서 어떤 별을 찾고 싶다고 가정해 봅시다. 프로그램이 선형 검색(linear search)을 이용해서 별 카탈로그의 첫 번째부터 차례대로 별을 찾는다면, 최악의 경우에 2,539,913개의 별을 모두 검사해야 할 수도 있습니다. 카탈로그가 별 이름에 따라 알파벳 순서로 정렬되어 있다면, 최악의 경우라도이진 검색으로는 22개의 별만 탐색하면 됩니다.

앞으로 볼 개념이해하기 글에서는 알고리즘을 자세하게 묘사하는 방법, 알고리즘을 자바스크립트로 구현하는 방법 그리고 알고리즘의 효율성을 분석하는 방법에 대해 설명해 보겠습니다.

사람들에게 어떤 알고리즘을 설명할 때에 따라서는 꼭 완벽하게 설명하지 않아도 됩니다. 케이크 조리법에서 요리할 때 달걀을 냉장고에서 꺼내기 위해 어떻게 냉장고를 열지, 달걀을 어떻게 깨는지 같은 자잘한 사항은 생략합니다. 이 정도는 알 것이라고 가정하는 것이죠. 사람들은 생략된 내용을 어떻게 채울지 직관적으로 알지만, 컴퓨터 프로그램은 그렇지 않습니다. 그러므로 컴퓨터 알고리즘은 완벽하게 작성해야 합니다.

프로그래밍 언어로 알고리즘을 구현하기 위해서는 알고리즘을 자세하게 이해해야 합니다. 문제에 입력값은 무엇인지, 출력값은 무엇인지, 어떤 변수를 만들어야 하고 초기값은 어떻게 설정해야 하는지, 또 마지막 출력값을 계산하기 위해서 어떤 중간 과정이 필요한지, 이 모든 과정이 단순 반복문을 이용해 쓸 수 있는 명령일까요?

이진 검색을 자세하게 서술하는 법을 살펴봅시다. 이진 검색의 주 원리는 현재 머물러있는 합리적 추측 범위를 계속 파악하는 것입니다. 추측 게임을 한다고 가정하고 1부터 100까지의 숫자 중 하나를 골랐습니다. 만일 25라고 추측하면 맞추고자 하는 숫자는 그것보다 큰 수라고 얘기해주고, 또 81으로 추측할 경우 숫자가 그보다 작다고 말해 준다면 정답은 26부터 80까지의 범위에 있다고 추측하는 것이 합리적일 것입니다. 아래 수직선에서 빨간 부분은 합리적 추측값이고 까만 부분은 배제되는 부분입니다.

매 회마다 추측값 한 개를 선택해서 바로 전에 나온 합리적 추측 범위를 둘로 나누어 비슷한 크기의 범위가 두 개 나오도록 합니다. 추측이 틀리면 값이 너무 높거나 너무 낮다고 말할 것이고, 이에 따라 합리적 추측값의 절반 범위를 제외할 수 있습니다. 예를 들어 합리적인 추측값의 범위가 26에서 80 이면, 이 절반인 $(26+80)/2$‍, 53 을 선택할 것입니다. 그리고 53이 정답보다 크다면 53에서 80까지 범위는 제외할 수 있고, 26에서 52 범위가 다시 합리적 추측 범위가 되어 범위의 크기를 절반으로 줄이는 겁니다.

추측 게임에서는 변수 몇 개를 사용하여 합리적 추측 범위를 여러 개 추적할 수 있습니다. 변수 $min$‍ 을 현재 최소 합리적 추측값이라고 하고 $max$‍ 를 현재 최대 합리적 추측값이라고 합시다. 문제의 입력값 은 상대방이 생각할 수 있는 가장 큰 숫자인 $n$‍입니다. 답이 될 수 있는 가장 작은 값은 1이라고 가정하지만, 가능한 가장 작은 값을 두 번째 입력값으로 취하도록 알고리즘을 수정하기는 쉽습니다.

다음은 추측 게임에서 이진 검색을 사용하는 방법을 단계별로 나타낸 것입니다:

알고리즘의 입력값과 출력값을 분명하게 설정하고 "평균을 구함 "이나 "끝냅니다" 같은 명령이 정확히 의미하는 바를 명시하면 훨씬 더 명확하게 설명할 수 있습니다. 하지만 지금은 이것으로 충분합니다.

다음에는 배열에서 이진 검색을 사용하는 방법을 알아보고 알고리즘을 코드로 바꾸는 방법에 대해서도 이야기해보겠습니다.

위 자료는 다트머스 대학교 컴퓨터 과학과의 토마스 콜먼(Thomas Cormen) 교수, 데빈 발컴(Devin Balkcom) 교수, 칸아카데미 컴퓨팅 커리큘럼 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.