본문 바로가기

(탈퇴) Reuent's Post/Algorithms

Algorithm #2. Search algorithm. - 2.3 Binary Search.


이번 주제는 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 구조를 이용하는
다른 방법을 사용하기 보단 이런 방식을 사용하는 것이 훨씬 경제적이겠지요.