우주의 IT 소행성

오늘은 가장 기초적인 알고리즘 중 하나인 이분 탐색 (이진 탐색)에 대해서 알아보겠습니다.

이분 탐색에 앞서 순차 탐색에 대해서 복습을 해볼 텐데요.

N개의 데이터가 들어있는 어떤 데이터의 모음 DATA가 있을 때 DATA의 0번째 데이터부터 N번째 데이터까지 모두 방문하여 탐색하는 것을 순차 탐색이라고 합니다.

# 리스트에서 주어진 1개의 값을 찾는 소스코드
data = [12, 255, 156, 8798, 15, 487, 212, 11, 98, 9, 878, 999, 445, 54563, 546779, 78]
print("탐색할 데이터는 : , end='')
target = int(input())

for i in data:
	if i == target:
    	print(target, "을 찾았습니다!")
    	break

당연히 N개의 데이터가 들어있으니 탐색에도 N번만큼의 시간이 소요되겠습니다.

그렇다면 데이터가 1억 개가, 10억 개가, 아니 1조 개가 넘게 유입되어도 과연 순차 탐색으로 탐색을 해낼 수 있을까요?

정답은 "아니오" 입니다.

실제 코딩 테스트나 실무에서 사용하게 되는 알고리즘은 항상 최적의 시간 복잡도를 가져야 합니다.

1조 개의 데이터를 1조 번만큼 탐색하지 않고 더 적은 횟수를 탐색하는 알고리즘이 있다면 정말 좋겠습니다.

그런 알고리즘이 바로 오늘 배울 이분 탐색 알고리즘입니다.

이분 탐색 알고리즘이란?

- 탐색 범위를 절반으로 줄여나가면서 탐색하는 알고리즘

조건 : 배열 내부의 데이터가 오름차순으로 정렬되어 있어야 함

사용 시점 (보편적) : 1000만 이상의 데이터 탐색할 때, 정렬되어 있는 데이터를 탐색할 때

장점

- 매우 빠르게 데이터를 찾을 수 있음

- 탐색 범위를 절반씩 좁혀나가며 데이터를 탐색함

- O(logN)의 시간 복잡도를 가짐

이분 탐색은 탐색 범위의 시작점, 끝점, 중간점 세 점 간의 비교로 원하는 데이터를 빠르게 찾아내는 알고리즘입니다.

이분 탐색에 대해서 간단히 알아보도록 하겠습니다.

먼저 1부터 100까지 오름차순으로 정렬된 리스트가 있다고 가정합시다.

이 리스트에서 이분 탐색을 이용해 67을 탐색해봅시다.

시작점 = start = 1

끝 점 = end = 100

중간점 = mid = (시작점 + 끝점) // 2 = 50

타겟(target)인 67이 중간점보다는 크고 끝 점보다는 작습니다.

오름차순으로 정렬되어있는 리스트이기 때문에 중간점부터 끝점 사이에는 50 ~ 100까지의 숫자만 들어있으므로

우리는 시작점 ~ 중간점 ( 1 ~ 50 )를 탐색할 필요가 없습니다.

따라서

시작점 = 50

끝 점 = 100

중간점 = 75로 수정을 해 줍니다.

이번에는 타겟이 시작점보다 크고 중간점 보다 작습니다 (start <= target <= mid)

따라서

시작점 = 50

끝 점 = 75

중간점 = 62로 수정을 해 줍니다.

계속해서 타겟을 찾을 때 까지 탐색 범위를 좁혀줍니다.

축하드립니다! 계속해서 반복하다보니 중간점에 우리가 그토록 찾던 타겟이 나타났습니다!

이처럼 탐색 범위를 절반의 절반으로 줄여가는 방법을 이분 탐색이라고 합니다.

1 ~ 100까지 전체 데이터의 개수는 100개 이지만 이분 탐색을 이용해 총 7번의 탐색으로 원소를 찾았습니다.

만약 순차 탐색이였다면 더 많은 시간이 소요되었을 것입니다.

이제 이분 탐색을 파이썬으로 구현해보겠습니다.

재귀 함수로 구현한 이분 탐색법

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)

반복문으로 구현한 이분 탐색법

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)

질문, 추가, 오류, 오타, 지적 환영합니다.