Binary Search (이진 탐색)

이진 탐색은 주어진 배열 A의 가운데 요소 (정수)를 탐색하는 키 요소랑 비교하고 배열 A를 왼쪽 오른쪽 하위배열들로 나눈다. 물론 가운데 요소가 키 요소보다 작으면 오른쪽 하위 배열에서 탐색을 시작하고 키 요소보다 크면 왼쪽 하위 배열에서 탐색을 시작한다. 이런 식으로 반복적으로 배열 A가 왼쪽/오른쪽 하위 배열들로 나뉘어진다 키 요소가 발견 되거나 배열 A가 더이상 나뉘어질 수 없을 때 까지.

 

 

여기서 전 글에 계시한 순차 탐색 (Linear Search)과 이진 탐색의 차이점을 들어난다. 순차 탐색은 배열 A가 정렬 되어있지 않은 상태로도 탐색이 가능하지만 이진 탐색의 조건은 배열 A가 이미 정렬되어야 있는 상태여야 한다. 안그러면 있는 요소를 제대로 못 찾을 수도 있다. 

 

 

 

비주얼을 아래에 첨부하겠다.

 

 

 

 

 

 

반복문을 써도 괜찮지만 가장 효율적인 방법은 재귀다 (recursion). 따라서 재귀로 알고리즘을 구현했다. 의사코드는 아래와 같다.

 

  Binary-Search(A, n, T)
    L := 0
    R := n - 1
    while L <= R do
        m := floor((L + R) / 2)
        if A[m] < T then
              L := m + 1
          else if A[m] > T then
            R := m - 1
        else:
            return m
    return unsuccessful

 

시간 복잡도 T(n)은 T(n / 2) + c (c는 상수)이다. 이 프로그램을 구현 할 때 재귀를 사용했기 때문에 공간 복잡도는 O(Logn)이다. 

 

 

아래 레포지토리에 이진 탐색 프로그램을 완성하였다. 참고하기 좋을 것 같다. 

 

 

GitHub - yoonBot/Algorithm-Library: a library of algorithms sorted by their categories.