태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.
블로그 이미지
Lonewolf dlbo

calendar

1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30          

Notice


이번 주제는 Binary Search. 즉, 이분 검색입니다.

왜 'Binary' 라는 표현이 나왔는지 궁금하실텐데요, 이는 검색 방식 때문입니다.

앞서 작성한 'Quick Sort' 알고리즘에서 'Divide and Conquer' 와 'Three of median' 기법을 설명 드렸을겁니다.
Binary Search 알고리즘은 이 기법들을 동시에 사용합니다.
단, 전제 조건은 '이미 정렬된 레코드' 에서 사용해야 한다는 전제조건이 붙죠.

그럼 알고리즘 소개를 해 볼까요.


1.  이 레코드의 중앙값을 찾는다. - 이미 정렬된 레코드라 가정한다. -

2. . 만약 찾을 key 값이 이미 찾아놓은 레코드의 중앙값과 같다면 Find it.

3. 먄약 찾지 못했다면
    3 - 1.              key 값보다 중앙값이 작은 경우, 탐색 범위의 최대치를 중앙값으로 선택.
    3 - 1 - 1.         반으로 줄어든 구간에 대한 중앙값을 찾는다.
    3 - 1 - 2 - 1.    만약 중앙값과 key 값이 같다면 Find it.
    3 - 1 - 2 - 2.    찾지 못했다면 3 으로 되돌아간다.

    3 - 2.              key 값보다 중앙값이 큰 경우, 탐색 범위의 최소치를 중앙값으로 선택.
    3 - 2 - 1.         반으로 줄어든 구간에 대한 중앙값을 찾는다.
    3 - 2 - 2 - 1.    만약 중앙값과 key 값이 같다면 Find it.
    3 - 2 - 2 - 2.    찾지 못했다면 3 으로 되돌아간다.

4. 탐색 범위가 0 이 된다면 Can't find it.

알고리즘을 수행할 수록 탐색 범위가 반으로 줄어들고, 줄어든 범위에 대해서 다시 같은 알고리즘을 재귀적으로
수행합니다. - 분할정복 -
그리고 중앙값을 찾기 위해 탐색 범위의 Min 값과 Max 값의 중간값을 선택합니다. - 중위법 -

-_-ㅋ 매우 간단한 알고리즘입니다.
하지만 굉장히 효율적이라 이미 라이브러리 함수로 내장되어 있기도 하죠.
O( N log N ) 의 효율을 자랑하는, 가장 대표적인 탐색법 중 하나입니다.
코드로 구현해 볼까요.



물론 미리 레코드를 정렬해야 한다는 번거로움이 있긴 합니다.
하지만 Quick Sort 후 Binary Search 를 하는 것은 매우 효율적인 코딩 기법 중 하나라고 생각합니다.

둘 모두 O( N log N ) 의 효을 보장해 주고, 코딩 역시 간단하므로 괜히 복잡하게 Tree 구조를 이용하는
다른 방법을 사용하기 보단 이런 방식을 사용하는 것이 훨씬 경제적이겠지요.
posted by 비회원

댓글을 달아 주세요

  1. 지나가다가 2012.06.21 08:43  Addr Edit/Del Reply

    바이너리서치는 o(logn) 속도를 갖는 탐색 기법입니다.
    o(nlogn)으로 쓰여있길래요~