이진탐색 (Binary Search) 알고리즘

이진탐색 (Binary Search) 알고리즘.


 N개의 데이터를 가진 배열 list[]가 있고, 우리가 찾고자 하는 값이 key라고 하자( list[0], list[1], ..., list[N-1] ).

이진 탐색은 배열의 중간요소(list[N/2])와 찾고자하는 값(key)을 비교한다. 찾고자하는 값이 중간요소 보다 작다면 배열의 중간요소 보다 큰 요소들(list[N/2] ... list[N-1])에는 찾고자 하는 데이터가 없는 것이다. 즉, 데이터의 절반은 검사 할 필요가 없어진다.

나머지 요소들에 대해 똑같이 반복한다. (Recusive)

 

탐색방법
    입력 : 리스트,시작인덱스,마지막인덱스,검색값

    출력 : 해당 키의 인덱스 ( 찾는 값이 있으면 ) 또는 아니오 ( 찾는 것이 없으면)

1. 각 값의 의미

    head : 찾고자 하는 리스트 의 처음
    tail : 찾고자 하는 리스트의 끝
    mid : head 와 end의 중간 값

2. 리스트의 중간에 있는 원소의 키(list[mid]) 와 탐색하려는 값 key를 비교 

    한다.

  이진 탐색 알고리즘

 +--------------------------------------------------------------------+

 |  1. 중간요소를 구한다. mid = (head + tail ) / 2                                    |

 |  2. 중간요소보다 key값이 크면, mid를 head 로 한다.                          |

 |  3. 중간요소보다 key값이 작으면, mid를 tail로 한다.                           |

 |  4. head <= tail인 동안 1에서 3을 반복                                               |

 |  5. 중간요소와 key가 같으면 찾았음, 그렇지 않으면 찾지 못함.           |

 +--------------------------------------------------------------------+

 

   key = 61

 

1) 중간요소를 구한다.

 

      ↓head                                                                ↓tail

   +-----+-----+-----+-----+-----+-----+-----+-----+-----+     

   |  24  |  36   |  37   |  45  |  57   |  61  |  69   |  81  |  95  |

   +-----+-----+-----+-----+-----+-----+-----+-----+-----+     

      [0]    [1]     [2]     [3]    [4]     [5]    [6]     [7]    [8]

                                           ↑

                                          mid = (head + tail) / 2

 

 

2) 중간요소보다 key값이 크면, mid를 head로 하고, 중간요소를 구한다.

 

                         ↓head                           ↓tail

   +-----+-----+-----+-----+-----+-----+-----+-----+-----+     

   |  24   |  36  |  37  |  45   |  57   |  61  |  69   |  81  |  95  |

   +-----+-----+-----+-----+-----+-----+-----+-----+-----+     

      [0]     [1]    [2]     [3]    [4]     [5]    [6]     [7]    [8]

                                                             ↑

                                                           mid = (head + tail) / 2

 

3) 중간요소보다 key값이 작으면, mid를 tail로 하고, 중간요소를 구한다.

 

                                           ↓head         ↓tail

   +-----+-----+-----+-----+-----+-----+-----+-----+-----+     

   |  24   |  36  | 37  |  45   |  57  |  61   |  69   |  81  |  95  |

   +-----+-----+-----+-----+-----+-----+-----+-----+-----+     

      [0]      [1]    [2]    [3]    [4]     [5]     [6]    [7]    [8]

                                                     ↑

                                                    mid = (head + tail) / 2

 

 

4) 중간요소 = key. 찾았음

 

                                           ↓head         ↓tail

   +-----+-----+-----+-----+-----+-----+-----+-----+-----+     

   |  24  |  36   |  37   |  45  |  57  |  61   |  69  |  81   |  95  |

   +-----+-----+-----+-----+-----+-----+-----+-----+-----+     

      [0]    [1]     [2]     [3]    [4]    [5]     [6]    [7]     [8]

                                                    ↑

                                                   list[mid] = key

 

 

 

이 이진 탐색 알고리즘은 간단하면서도 무척 빠르다. 이진 탐색의 큰 단점은 소트된 데이터에만 적용이 가능하다는 점이다. 따라서, 이진탐색을 하기전에 반드시 소트를 해야만 한다.

수시로 데이터가 입력되고 조회되어야 하는 온라인(on-line)시스템에서 이진 탐색을 사용한다는 것은 힘든 일이다. 데이터가 입력 될때 마다 소트를 해야하기때문이다. 그러나, 수집된 데이터를 하루 혹은 일주일 단위로 한꺼번에 처리하는 일괄처리(batch)작업에서는 아주 좋은 효과를 볼수있다.