Binary Search

이진 탐색은 배열 내부의 데이터가 정렬되어 있을 때, 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘이다. 이진 탐색은 위치를 나타내기 위해 시작점, 끝점, 중간점 변수를 사용한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정이다.

1. 이진 탐색 방법

위에 정렬된 데이터 15개에서 76의 데이터를 찾는다고 해보자.

step 1. 시작점은 [0], 끝점은 [14], 중간점은 [7]이다. 중간점에 위치한 데이터 47은 찾으려는 데이터 76보다 작으므로 47 이하의 데이터는 볼 필요가 없다. 따라서 시작점을 [8]로 변경한다.

step 2. 시작점은 [8], 끝점은 [14], 중간점은 [11]이다. 중간점에 위치한 데이터 77은 찾으려는 데이터 77보다 크므로 중간점 이후의 값은 확인할 필요가 없다. 따라서 끝점을 [11]의 이전인 [10]으로 옮긴다.

step 3. 시작점은 [8], 끝점은 [10], 중간점은 [9]이다. 중간점에 위치한 데이터 64는 찾으려는 데이터 76보다 작으므로 64 이하의 데이터는 볼 필요가 없다. 따라서 시작점을 [10]로 변경한다.

step 4. 시작점과 끝점은 [10]이다. [10]의 데이터 76은 찾으려는 데이터 76과 동일하므로 이 시점에서 탐색을 종료한다.

전체 데이터는 15개이지만, 이진 탐색을 이용해 총 4번의 탐색으로 원소를 찾을 수 있었다.
이진 탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)이다.

2. 이진 탐색 구현

2-1. 재귀 함수로 구현한 이진 탐색

# 이진 탐색 소스코드 구현(재귀 함수)
def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
        return binary_search(array, target, mid + 1, end)

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)


'''
input data: 
10 7
1 3 5 7 9 11 13 15 17 19
output data:
4
'''

2-2. 반복문으로 구현한 이진 탐색

# 이진 탐색 소스코드 구현(반복문)
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:    
            end = mid - 1
        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
            start = mid + 1
    return None

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)


'''
input data: 
10 7
1 3 5 7 9 11 13 15 17 19
output data:
4
'''

Reference

• http://blog.weirdx.io/post/3121 (이진 탐색 그림)