이진 탐색 (Binary-Search)

Perl로 배우는 알고리즘에서 좋은 내용을 발췌한다.



이진 탐색은 옛부터 알려진 탐색 방법중의 하나이며

어떠한 데이터를 우리가 원하는 테이블에서 검색을 할 때.

순차적으로 검색을 하는 것보다 더 효율적으로

반씩 끊어가면서 탐색을 하는 알고리즘을 이야기한다.


뜬구름 잡는 이야기 같아 죄송하지만...

실제코드부터 먼저 보기로 하자.

1 2 3 4 5 6 7 8 9 10 11

sub binary_search{ my ($array,$word) = @_; my ($low,$high) = (0, @$array -1); while( $low <= $high){ my $try = int( ($low+$high)/2); $low = $try+1, next if $array->[$try] lt $word; $high = $try-1, next if $array->[$try] gt $word; return $try; # 값을 찾았을 때 해당 값 리턴 } return; # 찾지 못했을 때는 undef }

저게 무엇인가.. 외계어인가? 뭥미? 후욱후욱


그래서 말로 한번 풀이해보려 한다.



하나의 배열에 A에서 H까지 저장이 되어있다고 생각하자.

  ( A B C D E F G H )

F라는 문자가 우리가 찾을 문자다.


처음부터 순차적으로 찾아나간다면...

6번을 검색한뒤 F를 찾을 수 있다.



자 이제 이진탐색을 한번 해보자.

일단 배열을 반으로 뚝...자른다.

그리고 그 반으로 자른 중간지점을 $try라고 치고 우리가 찾을 글자와 비교를 한다.

        요놈
          ↓
A B C (D) E F G H

$try 우리가 찾을 문자열(F)가 아니다.

그러면 이 중앙의 값($try)을 우리가 찾을 문자열과 비교하여

문자열이 이 값보다 크다면 위치를 한칸 이동을 시킨다.


   여기로 이동한다.
             ↓
A B C D (E) F G H

그리고 ABCD는 모두 버린다;;


어떤가??

단 한번의 검색만으로 F의 값에 근접해 가고 있지 않는가?

이제 이 4개의 테이블 만으로 검색을 해보자.


배열을 또 반으로 자른다.

  요놈
    ↓
E (F) G H

딱 걸렸다.

문자열을 찾았으니 이 값을 반환해주면 되는 것이다.

여기까의 검색횟수는 총 2번밖에 소요되지 않았다.



이렇게 절반씩 접근해서 찾기 때문에 굉장히 효율적이며

빠르게 검색하면서 찾아나간다.

그런데 여기에는 한가지 문제점이 있다.

우리가 검색할 테이블이 정렬이 되어 있어야 한다는 것!



문자열의 아스키코드 값을 비교하며 검색하는 형태이기 때문에

데이터가 정렬이 되어 있지 않다면

이 알고리즘은 대부분 무한루프가 돌 것이다.



자.. 이제 위의 소스를 다시한번 보길 바란다.

그리고 이해를 하려고 노력하자.

이해가 다 되셨다면 실제 코드에 적용시켜 활용해 보도록 하겠다.

bsearch.pl

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#!/usr/bin/perl # # bearch - 알파벳순으로 정렬된 리스트에서 단어를 탐색 # # 사용법 : bsearch word filename $word = $shift; # 첫번째 인자를 $word에 할당 chomp(@array = <>); # 파일의 단어들을 읽어드린다. # 줄바꿈 문자는 제거 (chomp) ($word,@array) = map lc,($word, @array); # 모두 소문자로 바꾼다. sub binary_search{ my ($array,$word) = @_; my ($low,$high) = (0, @$array -1); while( $low <= $high){ my $try = int( ($low+$high)/2); $low = $try+1, next if $array->[$try] lt $word; $high = $try-1, next if $array->[$try] gt $word; return $try; #값을 찾았을 때 해당 값 리턴 } return; #찾지 못했을 때는 undef }

http://codepad.org/mmb8qizI

이 코드를 실제로 적용시켜 테스트를 해봐도 좋다.


개인적인 소견으로는 저 perlish한 코드를 눈에 익히고 활용하려면...

perl을 꾀 오래 써야 겠다는 생각이 든다.