배열에 이진 검색 구현하기

정렬된 배열에서 이진 검색을 사용하는 방법을 배워봅시다. 자바스크립트와 다른 수많은 프로그래밍 언어는 이미 주어진 요소가 배열 안에 있는지, 만일 있다면 그 위치를 알려주는 메서드를 가지고 있습니다. 하지만 이런 메소드를 더 잘 이해할 수 있도록 직접 구현해 봅시다. 다음은 25개 소수가 차례대로 저장된 JavaScript 배열입니다.
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
예를 들어 숫자 67이 소수인지 알고 싶다고 합시다. 67이 배열 안에 있다면 67은 소수입니다.
또 67보다 작은 소수는 몇 개일지 궁금할 수 있습니다. 배열에서 67의 위치를 알아내면 이 정보로 67보다 작은 소수가 몇 개인지를 알아낼 수 있습니다.
어떤 요소의 배열 내 위치를 인덱스라고 합니다. 배열의 인덱스는 0부터 시작해서 하나씩 커집니다. 인덱스 0에 있는 요소는 배열 내 첫 번째 요소입니다. 어떤 요소가 인덱스 3에 있다면 그 앞에 세 개의 요소가 있음을 의미합니다.
아래 예시를 살펴봅시다. 왼쪽에서 오른쪽으로 소수의 배열을 읽어내려가면 (핑크 네모 속에 있는) 숫자 67을 배열 인덱스 18에서 찾을 수 있습니다. 이런 식으로 순서대로 숫자를 살펴보는 것을 선형 검색 이라고 합니다.
67이 인덱스 18에 있다는 것을 확인하면 67이 소수라는 것을 확인할 수 있습니다. 또한 배열 내에 67 밑으로 18개의 요소가 있다는 것, 즉 67보다 작은 소수는 18개라는 것을 금방 알 수 있습니다.
여기까지 몇 단계가 걸렸는지 보셨나요? 이진 검색이 더 효율적일 수 있습니다. primes 배열에는 25개의 소수가 포함되어 있기 때문에 배열의 인덱스 범위는 0부터 24까지입니다. 이전처럼 의사코드를 이용하여 min = 0 , max = 24로 설정하면서 시작합니다. 이진 검색에서의 첫 번째 추측값은 (0+24)/2, 즉 12번 인덱스에 있는 값입니다. primes[12]은 67인가요? 아닙니다, primes[12]는 41입니다.
찾고자 하는인덱스값은 12보다 클까요, 작을까요? 배열 내 값은 오름 차순으로 되어 있고 41 < 67이기 때문에 67이라는 값은 인덱스 12의 오른쪽에 있을 것입니다. 즉 12보다 큰 인덱스를 찾아봐야 한다는 것입니다. min을 12+1인 13으로 업데이트하고 max는 24로 놔둡니다.
다음에 추측해야 하는 인덱스는 무엇일까요? 13과 24의 평균값은 18.5이고 배열 인덱스는 반드시 정수여야 하므로 18로 반내림합니다. 이제 primes[18]이 67이라는 것을 확인할 수 있습니다.
답을 찾았으므로 이진 검색 알고리즘은 여기서 멈춥니다. 선형 검색에서는 19번의 추측이 이루어진 반면 여기서는 두 번만에 끝났습니다. 아래에서 이 과정을 다시 한번 설명하겠습니다:

의사코드(pseudo-code)

한 가지 예를 들어 이진 검색 알고리즘을 글로 설명했습니다. 글로 나타내는 방법도 좋지만 글로 표현하다 보면 내용에 차이가 생길 수도 있습니다. 글은 너무 짧거나 너무 길 수도 있고 또한 가장 중요한 것은 항상 정확할 수는 없다는 것입니다. 여기서 JavaScript나 Python과 같은 프로그래밍 언어로 이진 검색을 설명할 수도 있지만, 프로그램에는 엄청나게 많은 정보가 들어있습니다. 프로그래밍 언어에 따른 요구사항을 채울 부분과 또 잘못된 데이터, 사용자 에러, 시스템 에러 등에도 대처해야 합니다. 그러므로 코드만 공부하게 되면 코드에 적용된 알고리즘을 이해하기가 힘들어질 수 있습니다. 이런 점으로 인해 본문에서는 종종 프로그래밍 언어의 특징들과 글을 혼합하여 표현하는 의사코드로 알고리즘을 설명합니다.
다음은 배열 안에서 검색이 가능하도록 수정된 이진 검색 의사코드입니다. 입력값은 array라고 부르는 배열, array의 요소의 개수 n, 검색 대상의 수 target입니다. 결과값은 arraytarget의 인덱스 값입니다.
  1. min = 0 이고 max = n-1이라고 합니다.
  2. guess의 값은 maxmin의 평균값을 정수가 되도록 버림한 값입니다.
  3. array[guess]의 값이 target과 같다면 검색을 멈춥니다. 타겟을 찾았습니다. guess를 결과값으로 반환합니다.
  4. 추측값이 더 작다면 즉, array[guess] < target이라면, min = guess + 1으로 바꿉니다.
  5. 아니면 추측값이 더 큽니다. 그러면 max = guess - 1로 바꿉니다.
  6. 2 단계로 돌아갑니다.

의사코드의 구현

이제부터는 상황에 따라 말로 된 설명, 의사코드, 그리고 자바스크립트 언어를 번갈아서 사용할 것입니다. 프로그래머라면 의사코드를 이해하고 이를 원하는 언어로 바꿀 수 있어야 합니다. 그러므로 여기서 JavaScript를 사용해도 다른 언어로 의사코드를 쉽게 구현할 수 있어야 합니다.
의사코드를 어떻게 해야 자바스크립트 프로그램으로 바꿀 수 있을까요? 먼저 함수를 생성해야 합니다. 왜냐하면, 입력을 받아서 값을 반환하는 코드를 작성해야 하고, 또, 이 코드를 다른 곳에서 다른 입력값을 받아서 써야 하기 때문입니다. 함수(binarySearch 라고 합시다)의 매개변수로는 배열과 찾고자 하는 대상 값이 있고 반환할 값은 찾고자 하는 값의 위치를 나타내는 인덱스입니다.
이제 함수의 본체 코드로 들어가서 어떻게 구현할지 살펴봅시다. 6단계는 2단계로 돌아가라고 합니다. 반복문처럼 보이네요. for 문 또는 while 문 중 무엇을 써야 할까요? for 문을 꼭 사용하고 싶다면 그럴 수도 있지만 이진 검색에서 추측하는 인덱스는 for 문과 같이 순서대로 커지지 않습니다. 처음에는 인덱스 12번을 추측하고 그 후에는 계산하여 18번으로 추측했습니다. 그래서 while 문이 더 좋은 선택입니다.
추측 게임 알고리즘을 짤 때 만든 의사 코드에서는 중요하지 않았지만, 배열의 이진 검색에서는 한 가지 중요한 단계를 빠뜨렸습니다. 만약 찾고 싶은 숫자가 배열에 없다면 어떤 일이 일어날까요? 이 경우에는 binarySearch 함수가 돌려주어야 하는 인덱스값을 먼저 결정합니다. 이 값은 배열에서 인덱스가 될 수 없는 숫자여야 합니다. -1은 배열 내 인덱스가 될 수 없으므로 -1을 사용하기로 합시다. (사실 아무 음수 모두 괜찮습니다.)
추측을 더 이상 할 수 없다면 검색 대상 값이 배열에 존재하지 않는 것입니다. 이 예제의 primes 배열에서 검색 대상 10을 찾는다고 해봅시다. 그 대상이 배열 안에 존재한다면, 인덱스 값이 각각 3과 4인 7과 11사이에 있을 것입니다. binarySearch 함수가 실행되는 동안 minmax의 인덱스 값 변화를 보다보면, min 값이 3이 되고 max 값이 4가 되는 경우가 생깁니다. 그러면 추측값은 인덱스 3이 되는데 ((3 + 4) / 2 는 3.5로 버림하면 3이기 때문), primes[3]은 10보다 작고, min값이 4가 됩니다. minmax가 모두 인덱스 4이기 때문에 다음 추측값은 인덱스 4가 되고 primes[4]는 10보다 큽니다. 그에 따라 max 값이 3이 됩니다. min이 4이고 max가 3이라는 것은 무슨 뜻일까요? 가능한 추측값이 최소 4이고 최대 3이라는 뜻입니다. 이 조건을 성립하는 수는 없습니다! 따라서, 검색 대상인 10이 primes 배열에 없다고 결론내릴 수 있고, binarySearch 함수가 -1을 반환합니다. 일반적으로, maxmin보다 작아진다면, 검색 대상이 정렬된 배열에 존재하지 않는다는 것을 알 수 있습니다. 검색 대상이 배열에 없는 경우를 처리하는 이진 검색 의사코드는 다음과 같습니다.
  1. min = 0 이고 max = n-1이라고 합니다.
  2. max < min이면 검색을 멈춥니다: targetarray에 존재하지 않습니다. -1을 반환합니다.
  3. guess 의 값은 maxmin 의 평균값을 정수가 되도록 버림 한 값입니다.
  4. array[guess]의 값이 target과 같다면 검색을 멈춥니다. 타겟을 찾았습니다. guess를 결과값으로 반환합니다.
  5. 추측값이 더 작았다면 즉, array[guess] < target이라면, min = guess + 1으로 바꿉니다.
  6. 다른 경우로는 추측값이 더 클 수 있습니다. 그러면 max = guess - 1로 바꿉니다.
  7. 2단계로 돌아갑니다.
이제까지 함께 의사코드를 살펴보았습니다. 이제 스스로 이진 검색을 구현해 보세요. 의사코드 부분을 복습해도 괜찮습니다. 오히려 복습해보는 편이 좋습니다. 그러면 의사 코드를 프로그램으로 바꾸는 과정을 더욱 더 잘 이해할 수 있을 것입니다.

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