메뉴 건너뛰기

SAP 한국 커뮤니티

[요청]Binary Search의 원리에 대한 질문

수욕정이풍부지 2009.02.12 20:16 조회 수 : 3916

안녕하세요?


ABAP 4년차인데요..


늘상 사용하는 Binary Search이지만 ABAP에서의 근본적인 원리가 갑자기 궁금해져서 질문을 드립니다.


전산학과 출신이라서 기본적인 알고리즘은 알고 있습니다.


Search하고자 하는 필드의 순서대로 Sort를 한 후에


이진 트리를 이용하여 중간값과 찾고자하는 값을 비교하여 검색하기 때문에


대상건수가 많을수록 속도는 일반 Search에 비해서 기하급수적으로 빨라지겠죠..


예를 들어 1000 건을 대상으로 Search를 하게 되면


일반 Search는 1000/2  = n 이므로 평균 500번의 탐색속도를 가지게 될거고


Binary Search는 2ⁿ = 1000이므로 최대 10번 정도의 탐색속도를 가지게 되는 걸로 알고 있습니다.


 


그런데 프로그래밍을 하면서 일반 Search든 Binary Search든 중복되는 값이 있을때는


가장 첫번째 값을 찾아온다는 것은 이미 수많은 경험을 통해서 익히 알고 있습니다.


궁금한 것은 일반 Search는 순차적으로 Read하므로 위 결과가 당연하다고 생각되지만,


Binary Search는 중간값을 비교하는데 왜 항상 첫번째 값을 읽어오느냐 하는 것입니다.


 


아래와 같은 Internal Table이 있다고 가정하고 질문을 드리면


 


Index   A    B


--------------


  1       1    a  


  2       2    b


  3       3    c


  4       3    d


  5       4    e


  6       5    f


  7       6    g


 


위에서 Internal table은 A라는 필드로 이미 Sort가 되어 있는 상태입니다.


 


여기서 READ TABLE itab WITH KEY A = '3' BINARY SEARCH 라는 명령을 하게 되면


세번째 Index를 읽게 되고 B값은 'c'가 될 겁니다.


하지만 알고리즘 접근을 하게 되면 총 7건의 Record이므로 중간값인 4번째 index를


읽어서 B값은 'd'가 되어야 맞는게 아닌가 하는 의문이 문득 들었던 적이 있었거든요..


 


ABAP에서 Bianry Search를  할 때 알고리즘을 어떻게 적용해서 사용하는건지 알고 싶네요.


물론 실질적인 프로그래밍을 함에 있어서는 쓸데없는 질문이 될수도 있겠지만  궁금한 건 못참는 성격이라서.. ^^


다시 한 번 말씀드리지만 Search 결과를 물어보고자 하는게 아니라


중복값의 Search가 정확히 어떤 방식으로 이루어지는지 혹시 알고 계시면 답변 주시면 감사하겠습니다. 


다들 수고하세요~


 

번호 제목 글쓴이 날짜 조회 수
6267 [요청]인터널 테이블을 이용한 필드 카탈로그를 가져올 때..... [5] 효방 ^-^ 2008.09.19 4239
6266 <b>[완료]</b>PFCG(롤생성 및 권한 관리)에 관해서 궁금합니다 [4] chanmaniac 2008.06.11 4229
6265 [re] Static Method와 Instance Method의 차이 좀 알려주세요. file sapjoy 2007.08.06 4213
6264 [요청]스마트 폼에서 바코드를 출력할 때, 페이지 포맷에 관해..... [3] Seph 2008.09.10 4192
6263 [re] 데이터 발췌 방법 [3] file sapjoy 2007.01.30 4188
6262 백그라운드 실행에 대해서 [2] 강진규 2007.04.03 4184
6261 <img src=3.gif>엑셀 업로드 시 이런경우가 발생할 수 있는지요. [7] 열공합시다 2010.12.30 4182
6260 <b>[완료]</b>Number RANGE OBJEC 삭제는 어디서 하나요? [3] 예슬짱 2008.12.09 4178
6259 [요청]MB1A BAPI명 어떤건가요? [4] 벤또 2007.11.08 4175
6258 <img src=3.gif>select 관련 질문 하나 드립니다. 답변을 애타게 기다립니다 ㅠ [13] 초밥 2010.12.01 4162
6257 <img src=3.gif>BAPI_INCOMINGINVOICE_CREATE 사용해 보신분요.. [2] 지니 2011.01.19 4153
6256 <b>[완료]</b>Func ALV에서 라인별 control 질문 [5] w 2007.10.11 4125
6255 <b>[완료]</b>if문 안에서의 commit work rollback work 구문개념좀 부탁드려요 [4] 아밥시작4일 2008.08.13 4123
6254 <img src=2.gif>급해요 !!! 화면에 옵션설정 하는 방법좀 알려주세요 . 옵션창이 어딨는지는 압니다. 그림첨부해요 [12] file 오렌지겅주님 2010.08.06 4121
6253 <img src=3.gif>Open SQL 에서 substring 하는 방법 [2] 모포 2010.06.23 4117
6252 <img src=2.gif>은행 계좌번호가 0으로 시작하는 경우 엑셀 다운로드시 문제점.. [6] 삼색볼펜 2010.03.22 4113
6251 HINTS ?, 아래와 같이 쓰는 구문의 차이가 뭔지 알 수 있을까요? [6] 김창훈 2007.08.15 4109
6250 <b>[완료]</b>Carry out repairs in non-original system only if they are urgent???? [9] SD2 2008.11.21 4105
6249 [요청]alv register_edit_event 메소드 사용!! [6] genius 2008.04.15 4105
6248 [요청]ALV 에서 checkbox 비활성 가능한가요? [1] 파파 2008.07.17 4094