Binary Search Algorithm

[ 이진 탐색 알고리즘 ]

이진 탐색 알고리즘(Binary Search Algorithm)은 리스트에 존재하는 특정 값을 찾기 위해서 리스트의 범위를 절반씩 좁혀가며 찾는 알고리즘이다. 처음부터 끝까지 값을 비교하는 순차 탐색에 비해 이진 탐색 알고리즘은 속도가 월등하게 빠르다. 이진 탐색은 시작, 끝 그리고 중간에 있는 데이터의 인덱스를 통해 범위를 줄이고 비교대상을 찾는다.

 

다만 이진 탐색 알고리즘을 사용할 때는 리스트 안의 값들이 이미 정렬이 되어 있어야 한다. 정렬이 되어 있지 않은 리스트에서는 이진 탐색 알고리즘을 사용할 수 없다. 그러므로 Mege Sort나 Quick Sort 등을 사용해서 리스트를 먼저 정리하고 이진 탐색을 사용해야 하는 것이다.

 

정렬이 완료된 리스트에서 범위를 절반을 나누어 찾고자 하는 값과 비교한다. 찾고자 하는 값이 중간보다 작을 경우 절반으로 쪼개진 왼쪽에 있는 리스트를 선택하고 값이 중간보다 클 경우 절반으로 쪼개진 오른쪽에 있는 리스트를 선택해서 원하는 값을 찾는다. 만약 값이 작다면 왼쪽 리스트를 선택하고 또다시 중간값을 확인하여 비교하는 과정을 반복한다.

 

 

 

[ 이진 탐색 예제 ]

(1) 17을 찾는다고 했을 때 값의 중간인 11을 선택한다.

그 이후 11과 17을 비교해보니 11보다 17이 더 커서 오른쪽 리스트를 선택하게 된다.

 

(2) 오른쪽 리스트에서 다시 중간인 19를 선택한다.

그 이후 19와 17을 비교해 보니 19보다 17이 작아서 왼쪽 리스트를 선택하게 된다.

 

(3) 외쪽 리스트에서 다시 중간인 13을 선택한다.

그 이후 13과 18을 비교해 보니 13보다 17이 더 커서 오른쪽 리스트를 선택하게 된다.

 

(4) 이제 비교 대상이 존재하지 않고 자기 자신만 남게되면서 이진 탐색은 끝난다. 

 

 

위 수행 내역을 파이썬 코드로 구현하면 아래와 같다. 

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    print("mid는 " + str(array[mid]) + " 이다.")
    
    if array[mid] == target:
        print("mid는 " + str(array[mid]) + " 이고 자기자신이다.")
        return mid
    elif array[mid] > target:
        print("target보다 중간값이 더 크다.")
        print("왼쪽 리스트를 선택한다.")
        print("탐색 리스트는 " + str(array[start:mid-1]) + " 이다.\n")
        return binary_search(array, target, start, mid -1)
    else:
        print("target보다 중간값이 더 작다.")
        print("오른쪽 리스트를 선택한다.")
        print("탐색 리스트는 " + str(array[mid + 1:end]) + " 이다.\n")
        return binary_search(array, target, mid + 1, end)

array = [2,5,7,8,11,13,17,19,23,29]
n = len(array)
target = 17

result = binary_search(array, target, 0, n - 1)
if result == None:
    print("찾는 원소가 리스트에 없다.")
else:
    print(result + 1)

########################################
> mid는 11 이다.
> target보다 중간값이 더 작다.
> 오른쪽 리스트를 선택한다.
> 탐색 리스트는 [13, 17, 19, 23] 이다.

> mid는 19 이다.
> target보다 중간값이 더 크다.
> 왼쪽 리스트를 선택한다.
> 탐색 리스트는 [13] 이다.

> mid는 13 이다.
> target보다 중간값이 더 작다.
> 오른쪽 리스트를 선택한다.
> 탐색 리스트는 [] 이다.

> mid는 17 이다.
> mid는 17 이고 자기자신이다.
> 7