[EKOO의 JAVA를 이용한 자료구조:9회] Searching (2)

[EKOO의 JAVA를 이용한 자료구조:9회] Searching (2)

저자:EKOO| 날짜: 2005년 06월 14일

 

Binary Search

 이진 검색이라고도 합니다. 지난번 강좌에서 Binary Search Tree에 대해서 배우신거 기억 나시나요? Binary Search Tree는 자식노드를 최대 두개까지 가질 수 있으며, 왼쪽 자식이 오른쪽 자식보다 작아야 한다는 규칙이 있었습니다. Binary Search는 평균적으로 상당히 빠른 검색시간을 보여주는 검색 방법입니다.

 실제로 Binary Search가 어떻게 돌아가고, 또 어떻게 구현하는지에 대해서 알아보도록 하겠습니다.

[그림 3] Array안에 들어있는 숫자들.(오름차순)
 위와 같은 배열에 숫자들이 일정한 순서에 의해서 나열되어 있습니다. Binary Search를 사용하려면 찾기위한 대상이 반드시 어떤 순서에 의해서 정렬이 되어 있어야만 합니다. 그 이유에 대해서는 실제 코드를 보고, 찾는 그림을 보고 난 후 말씀드리도록 하겠습니다. 일단 실제로 어떻게 찾나 애니메이션으로 보도록 하죠.

[그림 4] Binary Search를 이용한 검색 단계
 위의 애니메이션 처럼 단계가 되는데요. 이를 코드로 구현해 보면 아래의 그림과 같습니다. 재귀함수로 구현이 되어 있습니다.

public static int Search(int[] a, int first, int size, int target) {   int middle;   if( size <= 0 )     return -1;   else   {     middle = first + (size / 2);     if( target == a[middle] )       return middle;     else if( target < a[middle] )       return Search(a, first, size / 2, target);     else       return Search(a, middle + 1, (size - 1) / 2, target);   } }

 48이란 숫자가 배열의 어느 index에 위치해 있는가를 알려줍니다. 위의 그림처럼 코드로 구현이 되는군요. 종이를 하나 준비하시고 실제로 size와 first, middle을 따라가 보시면 쉽게 이해하실 수 있습니다. 위의 코드를 보시면 target과 a[middle]을 비교하여 검색할 부분을 정해주는데, 만약 a배열의 정렬 조건과 부등호가 맞지 않는다면 원하는 결과를 얻지 못하게 됩니다.

 만약에 위의 배열에서 48을 찾는데 Serial Search를 사용한다면 5번의 과정을 거쳐야 합니다. 하지만 Binary Search를 이용하였더니 단 3 단계 만에 원하는 결과를 얻어내었습니다. Best case의 시간은 물론 Serial Search 보다 나쁘지만 Average case나 Worst case의 경우에는 Serial Search 보다 더욱 좋은 검색 시간을 보입니다.