안녕하세요?

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가 정확히 어떤 방식으로 이루어지는지 혹시 알고 계시면 답변 주시면 감사하겠습니다. 

다들 수고하세요~