이진 탐색 정복기2 - 이진 탐색이란..-

1. 이진 탐색(binary search)

 

배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘

 

데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다

 

범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다

 

위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 그리고 중간점이다.

 

찾으려는 데이터와 중간점 위치의 데이터를 반복적으로 비교하여 원하는 데이터를 찾는게 이진 탐색이다.

 

이미 10개의 정렬된 데이터에서 값이 4인 원소를 찾는 예시를 살펴보자

 

 

1) 먼저 시작점과 끝점을 확인하고 둘 사이에 중간점을 정한다

 

시작점은 0, 끝점은 9이고 중간점은 4.5인데 중간점이 실수면 소수점 이하를 버린다

 

그래서 중간점은 4이다.

 

2) 다음으로 중간점 4의 데이터인 8과 찾고자하는 데이터 4의 값을 비교하자.

 

중간점의 데이터가 더 크다면 이미 데이터가 정렬되어 있으므로, 중간점 이후의 데이터는 볼 필요도 없다

 

3) 끝점을 중간점 이전인 3으로 옮긴다.

 

 

1) 이제는 시작점이 0이고 끝점이 3이다. 중간점은 1.5인데 소수점 이하를 버려서 1이 된다.

 

2) 그런데 중간점 1의 데이터 2는 찾고자 하는 데이터 4보다 작으므로, 중간점 이전의 데이터는 볼 필요도 없다.

 

3) 그래서 시작점을 중간점 이후인 2로 변경함

 

 

1) 이번엔 시작점이 2이고 끝점이 3이며 중간점은 2.5에서 소수점 이하를 버려서 중간점은 2이다.

 

2) 중간점에 위치한 데이터 4는 찾고자하는 데이터 4와 일치하므로 탐색을 종료한다.

 

위와 같이 탐색하면 전체 데이터는 10개였지만 3번만에 4를 찾아낼 수 있었따.

 

이진 탐색은 한번 확인할 때마다 확인해야하는 원소의 개수가 절반씩 줄어들어서 시간 복잡도가 O(logN)이다.

 

 

2. O(logN)의 의미?

 

한 단계를 거칠때마다 확인하는 원소가 평균적으로 절반으로 줄어든다.

 

예를 들어 데이터의 개수가 32개이면 1단계만 거치면 이상적인 경우에는 16개가량 데이터가 남는다

 

2단계를 거치면 8개가량의 데이터만 확인하면 된다.

 

즉 단계마다 2를 나누는 것과 동일하므로 연산 횟수는 $log_{2}N$과 비례한다.

 

이를 O(logN)으로 표기한다.

 

 

3. 구현 예시

 

재귀함수를 이용하여 구현하거나 반복문을 이용하여 구현할 수 있다

 

3-1) 재귀함수를 이용한 구현을 살펴보면,

 

시작점이 끝점보다 크다면 None을 반환하고

 

중간점 mid = (start+end)//2로 구할 수 있다

 

이렇게 하면 int()함수 사용하지 않고 모든 경우에 중간점을 구할 수 있다

 

다음 중간점과 찾고자하는 데이터 target을 비교하여.. 서로 일치하면 중간점 index를 반환하고

 

중간점이 더 크다면 오른쪽은 볼 필요가 없으므로, end를 중간점-1로 보낸다

 

중간점이 더 작다면 왼쪽은 볼 필요가 없으므로 start를 중간점+1로 보낸다

 

#이진 탐색 재귀적 구현

def binary_search(array, target, start, end):
    
    if start > end:
        
        return None
    
    mid = (start + end)//2

    #중간점 데이터와 target이 동일하면 중간점 index를 반환
    if array[mid] == target:
        
        return mid
    
    #중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽을 확인
    elif array[mid] > target:
        
        #end를 중간점의;왼쪽으로 보낸다
        return binary_search(array, target, start, mid-1)
    
    #중간점의 값보다 찾고자 하는 값이 큰 경우에 오른쪽을 확인
    else:
        
        #start를 중간점의 오른쪽으로 보낸다
        return binary_search(array, target, mid+1, end)

 

예시를 입력받아보면

 

#원소의 개수 n과 찾고자 하는 문자열 target을 입력받는다

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

#전체 원소를 입력받는다

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

#이진 탐색의 수행 결과를 출력

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

if result == None:
    
    print('원소가 존재하지 않습니다.')

else:
    
    print(result+1) #중간점의 위치(인덱스가 0부터 시작해서 1을 더함)
    
    
10 7
1 3 5 7 9 11 13 15 17 19
4

10 7
1 3 5 6 9 11 13 15 17 19
원소가 존재하지 않습니다.

 

3-2) 반복문으로 구현

 

중간점을 mid = (start+end)//2로 찾고 중간점의 데이터와 찾고자 하는 데이터가 같다면 mid를 바로 return한다

 

반대로 중간점의 데이터가 더 크다면 오른쪽은 볼 필요도 없으므로 end를 mid-1로 옮기는 end = mid-1

 

중간점의 데이터가 더 작다면 왼쪽은 볼 필요도 없으므로 시작점 start를 mid+1로 옮기는 start = mid+1

 

#이진 탐색 반복문 구현

def binary_search(array, target, start, end):
    
    #시작점이 끝점보다 작거나 같을때만 반복
    #시작점이 끝점보다 커지면 반복을 종료
    while start <= end:
        

        mid = (start + end)//2 #중간점을 구한다

        #중간점의 데이터가 찾고자 하는 값과 일치하면 중간점 인덱스를 반환
        if array[mid] == target:
            
            return mid

        #중간점의 데이터가 찾고자하는 값보다 크다면 오른쪽은 볼 필요도 없다
        #끝점을 중간점-1로 옮긴다 
        elif array[mid] > target:
            
            end = mid-1
        
        #중간점의 데이터가 찾고자하는 값보다 작다면 왼쪽은 볼 필요도 없다.
        #시작점을 중간점+1로 옮긴다
        else:
            
            start = mid+1
    
    #찾지 못하면 반복문이 탈출되어 None을 반환
    return None

 

4. 부가설명

 

이진 탐색이 구현 코드를 보면 단순해보이지만 참고할 소스코드가 없이 구현한다면 상당히 어려울 수 있다

 

생각하는 프로그래밍(2014)의 저자 존 벤틀리는 이진 탐색 코드를 제대로 작성하는 프로그래머는 10%내외라고 말할 정도로 실제 구현은 까다롭다

 

자주 작성해보면서 암기하는 것이 많은 도움이 된다

 

이진 탐색의 원리는 다른 알고리즘에서도 폭넓게 적용되는 원리와 유사하므로 매우 중요하다

 

탐색 범위가 2000만을 넘어가는 매우 큰 상황에서 데이터를 절반씩 줄여가면서 탐색하는 O(logN)의 속도를 내는 이진 탐색같은 알고리즘을 떠올려보도록 하자

 

5. 연습문제

 

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

6. 풀이

 

위에서 배운 이진 탐색을 그대로 구현하면 되는 문제

 

위치를 찾는게 아니고 존재하냐 아니냐를 묻고 있으니, target과 array[mid]가 일치하면 1을 return하고 

 

반복문이 끝날때까지 찾지 못하면 0을 return

 

from sys import stdin

def binary_search(array,target,start,end):
    
    while start <= end:
        
        mid = (start+end)//2

        if array[mid] == target:
            
            return 1
        
        elif array[mid] > target:
            
            end = mid-1
        
        else:
            
            start = mid+1
    
    return 0

n = int(stdin.readline())

array = list(map(int,stdin.readline().split()))

m = int(stdin.readline())

m_array = list(map(int,stdin.readline().split()))

array.sort()

for target in m_array:
    
    print(binary_search(array,target,0,n-1))