이진 탐색 Binary Search

이진 탐색은 탐색 알고리즘 중 하나로, 이분 탐색이라고도 한다.

 

이진탐색 혹은 이분 탐색은 말 그대로 탐색하고자 하는 데이터를 반으로 나누어 탐색해간다는 의미이다.

 

위와 같은 데이터에서 17이라는 데이터를 찾는다고 가정하자.

for 혹은 while과 같은 반복문을 통해서도 빠른 시간 내에 값을 찾을 수 있겠지만, 이진 탐색을 적용해 찾는 과정을 살펴보자.

 

이진 탐색을 적용하기 위해 array 데이터를 정렬해주었다.

이진 탐색은 반드시 정렬된 데이터에서만 사용할 수 있다.

 

그리고 우리는 이 array에서 17이라는 데이터를 찾고자 한다고 가정하자.

먼저 위에서 언급한 대로 반복문을 통해 0번 인덱스부터 탐색을 한다면 9번만에 찾을 수 있다.

지금은 array 데이터의 크기가 작아 충분히 작은 시간이지만, 데이터가 만약 100만개, 1억개라면 최악의 경우 100만번, 1억번의 연산을 수행해야 한다.

 

이진 탐색을 적용하기 위해서는 위에서 언급한 듯이 데이터를 반으로 나누어야 한다. 정렬된 데이터의 중앙 값을 기준으로 데이터를 나눈다.

데이터의 중앙 값을 찾기 위해 (0 + 9)//2를 통해 중앙 인덱스 값을 찾아주었다.

중앙 값의 인덱스를 찾을 때에는 시작점과 끝점의 인덱스의 중간 인덱스를 구하면 된다. (정수부만 이용한다.)

우리가 찾고자 하는 값은 17이므로 파란색으로 표시한 중앙 값과 17을 비교하면, 17이 중앙 값보다 더 큰 것을 알 수 있다.

따라서 중앙 값과 그보다 작은 값들은 이제 탐색에서 제외하고 다시 탐색을 시작한다.

 

회색으로 표시한 부분은 이전 탐색에서 더이상 탐색하지 않기로 한 부분이다.

새로 탐색하기로 한 부분에서 다시 같은 동작을 반복하므로, 17과 새로운 중앙 값인 15를 비교한다.

이번에도 17이 중앙 값인 15보다 크므로, 중앙 값 15와 그보다 작은 값들은 모두 탐색에서 제외한다.

 

이전 탐색에서 탐색하지 않기로 한 부분을 다시 회색으로 표시했다.

남은 데이터에서 새 시작점과 끝점을 표시하고 중앙 값을 구한다.

중앙 값과 찾고자 하는 값을 비교해보니, 일치함을 알 수 있고 이로서 탐색이 끝났다.

 

정렬된 데이터 기준으로, 반복문을 사용했을 때에는 총 9번의 반복을 진행해야 했지만 이진 탐색을 이용해 3번만에 끝낼 수 있었다.

 

데이터가 고작 10개밖에 되지 않은 상황에서도 유의미한 탐색 횟수의 감소를 얻었고 데이터가 커질수록 이 효과는 증가할 것이다.

 

정렬된 데이터 기준으로, 반복문을 사용하면 O(N)의 시간 복잡도를 가지지만 이진 탐색을 사용하면 O(logN)의 시간 복잡도를 통해 값을 구할 수 있다.

 

+) 알고리즘 시간 복잡도 표현에서 log는 통상 밑이 2인 로그를 의미한다.

 

아래는 파이썬 코드로 나타낸 이진 탐색이다.

# 이진탐색 함수

# 이진 탐색은 정렬된 자료에서만 사용할 수 있고 O(logN)의 시간복잡도를 가진다.

# 정렬된 배열인 par_array이 필요
# 찾고자 하는 값인 target 필요
# 탐색이 진행되며 시작점인 start 필요
# 탐색이 진행되며 끝점인 end 필요
def BinarySearch(par_array, target, start, end):
    if start > end:
        return None
    
    # 이진탐색을 위한 인덱스 쪼개기
    # 정수부만을 이요하므로 //연산자 사용
    mid = (start + end)//2

    if par_array[mid] == target:
        return mid
    elif par_array[mid] > target:
        return BinarySearch(par_array, target, start, mid-1)
    elif par_array[mid] < target:
        return BinarySearch(par_array, target, mid+1, end)

n, target = map(int, input().split())

array = list(map(int, input().split()))

result = BinarySearch(array, target, 0, n-1)

if result == None:
    print("there is no target in array")
else:
    print("index of target in array is", result)