파이썬 이진 탐색(Binary Search) 완벽 가이드: 개념부터 구현까지

파이썬 이진 탐색은 정렬된 배열에서 특정 항목의 위치를 찾는 알고리즘입니다. 리스트를 절반씩 나누어 탐색하며, 찾으려는 값이 중간 값보다 크면 오른쪽 절반에서, 작으면 왼쪽 절반에서 검색을 계속 진행합니다.

리스트 안에서 특정 항목의 위치를 어떻게 찾을 수 있을까요? 그 해답이 바로 이진 탐색입니다. 이진 탐색을 활용하면 정렬된 배열 속 요소의 위치를 아주 효율적으로 찾아낼 수 있습니다.

컴퓨터는 리스트를 뒤져서 특정 항목을 찾는 데 매우 능숙합니다. 컴퓨터가 리스트에서 항목을 찾기 위해 사용하는 규칙을 '탐색 알고리즘'이라고 부르며, 그중 가장 널리 쓰이는 파이썬 알고리즘 중 하나가 바로 이진 탐색입니다.

이 글에서는 이진 탐색이 무엇인지, 어떻게 동작하는지 살펴보고, 실제 파이썬 코드 예시를 통해 직접 구현하는 방법까지 단계별로 알려드리겠습니다.

파이썬 이진 탐색이란?

파이썬 이진 탐색은 정렬된 배열에서 특정 요소의 위치를 찾아내는 알고리즘입니다. 리스트를 반복적으로 두 부분으로 나눈 뒤, 찾으려는 값이 리스트의 중간 값보다 큰지 작은지를 비교하며 탐색 범위를 좁혀 나갑니다.

이진 탐색을 구현하는 방법에는 두 가지가 있습니다. 두 방식 모두 배열 내 특정 시점의 최댓값 위치와 최솟값 위치를 추적하기 위한 포인터(pointer)를 설정한다는 공통점이 있습니다.

첫 번째 방식은 반복(iterative) 방식입니다. 일련의 문장을 반복 실행하면서 배열 내 요소의 위치를 찾아내며, 파이썬에서는 주로 while 루프를 사용합니다.

두 번째 방식은 재귀(recursive) 방식입니다. 자기 자신을 계속 호출하는 함수를 작성하여 리스트에서 원하는 요소를 찾을 때까지 탐색을 반복합니다. 재귀 방식은 앞서 설명한 '분할 정복(divide and conquer)' 접근법을 활용합니다.

이진 탐색 동작 원리: 단계별 예시

분할 정복이나 재귀 같은 용어만 들으면 이진 탐색이 실제로 어떻게 작동하는지 감이 잘 잡히지 않을 수 있습니다. 그래서 지금부터 구체적인 예시를 통해 이진 탐색의 동작 과정을 하나씩 살펴보겠습니다. 다음 리스트를 보세요.

이 리스트에서 숫자 22를 찾아보겠습니다.

먼저 리스트에 두 개의 포인터를 설정합니다. 하나는 리스트의 최댓값 위치를, 다른 하나는 최솟값 위치를 나타냅니다.

다음 단계는 배열의 중간 요소를 찾는 것입니다. 여기서 중간 값은 14입니다. 만약 이 값이 우리가 찾는 값과 같다면 그대로 반환하면 됩니다.

하지만 이 경우 14는 22와 다르므로, 프로그램은 비교 작업을 수행해야 합니다.

찾으려는 숫자가 중간 값보다 크다면 현재 중간 요소 기준 오른쪽에 있는 요소들과 비교하고, 그렇지 않다면 왼쪽에 있는 요소들과 비교합니다.

22는 14보다 크므로, 프로그램은 오른쪽 절반의 중간 요소와 22를 비교합니다. 그 값은 바로 22로, 우리가 찾던 숫자와 일치합니다!

원하는 값을 찾았습니다. 이제 프로그램은 해당 숫자의 인덱스 위치를 반환합니다. 이 경우 22의 인덱스는 3입니다 (참고로 파이썬 리스트는 0부터 인덱싱됩니다).

파이썬으로 이진 탐색 구현하기

이제 직접 파이썬 코드를 작성해 보겠습니다. 앞서 소개한 두 가지 방식, 즉 반복 방식과 재귀 방식으로 각각 이진 탐색을 구현해 보겠습니다.

방법 1: 반복문(Iterative)을 이용한 이진 탐색

먼저 반복문 방식입니다. 리스트의 항목들을 루프로 순회하며 중간 값을 찾고, 원하는 값을 발견할 때까지 이 과정을 반복합니다.

탐색 함수 작성하기

이진 탐색을 수행하는 파이썬 함수부터 정의해 보겠습니다:

def findValue(numbers, number_to_find):
	low = 0
	high = len(numbers) - 1

	while low <= high:
		middle = low + (high - low) // 2

		if numbers[middle] == number_to_find:
			return middle
		elif numbers[middle] < number_to_find:
			low = middle + 1
		else:
			high = middle - 1
	return -1

이 함수는 두 개의 매개변수를 받습니다. 탐색 대상인 리스트와, 리스트에서 찾고자 하는 숫자입니다.

그다음 리스트의 최솟값과 최댓값의 기본값을 저장할 두 개의 변수를 선언합니다. low는 0으로 설정되는데, 이는 리스트의 시작 인덱스입니다. high는 리스트 길이에서 1을 뺀 값으로 설정됩니다 (인덱스가 0부터 시작하기 때문입니다).

다음으로 while 루프를 선언합니다. 이 루프는 low가 high보다 작거나 같은 동안 실행되며, 즉 아직 원하는 숫자를 찾지 못했을 때만 계속 돌아갑니다.

루프 안에서는 중간 값(middle)을 계산합니다. high에서 low를 빼고, 그 결과를 2로 나눈 몫(// 연산자 사용)을 구한 뒤 low에 더하는 방식입니다. 이렇게 하면 오버플로우 없이 항상 올바른 중간 인덱스를 얻을 수 있습니다.

• 중간 값이 찾으려는 숫자와 같으면 → 해당 위치(인덱스)를 반환합니다.
• 중간 값이 찾으려는 숫자보다 작으면 → low를 middle + 1로 갱신하여 오른쪽 절반을 탐색합니다.
• 중간 값이 찾으려는 숫자보다 크면 → high를 middle - 1로 갱신하여 왼쪽 절반을 탐색합니다.

이 과정은 low가 high보다 작거나 같을 때까지 반복됩니다. 만약 값을 끝내 찾지 못했다면 -1을 반환합니다. 그 이유는 잠시 후에 설명하겠습니다.

탐색 실행하기

프로그램 마지막에, findValue 함수 외부에 다음 코드를 추가하세요:

numbers = [7, 9, 14, 22, 34]
number_to_find = 22

final = findValue(numbers, number_to_find)

if final == -1:
	print("This item was not found in the list.")
else:
	print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")

먼저 탐색 대상 리스트를 선언하고, 찾고 싶은 숫자로 22를 지정했습니다.

그다음 findValue() 함수를 호출하면서 리스트와 찾을 숫자를 전달합니다.

여기서 앞서 언급한 -1이 등장합니다. 함수가 -1을 반환했다면 해당 항목이 리스트에 없다는 의미입니다. 프로그래머들이 이런 상황에서 -1을 즐겨 사용하는 이유는, 유효한 인덱스는 음수가 될 수 없기 때문입니다.

-1이 아니라면, 프로그램은 해당 값의 인덱스 위치를 알려주는 메시지를 출력합니다.

실행 결과는 다음과 같습니다:

The number 22 was found at index position 3.

숫자 22가 인덱스 3번 위치에 있다는 것을 확인했습니다.

방법 2: 재귀(Recursive)를 이용한 이진 탐색

재귀 호출을 통해서도 이진 탐색을 구현할 수 있습니다. 원하는 숫자를 찾을 때까지 스스로를 계속 호출하는 함수를 정의하는 방식입니다.

재귀 함수 정의하기

앞선 예시처럼, 먼저 이진 탐색을 수행하는 함수를 작성합니다:

def findValue(numbers, number_to_find, low, high):
	if high >= low:
		middle = low + (high - low) // 2

		if numbers[middle] == number_to_find:
			return middle
		elif numbers[middle] < number_to_find:
			return findValue(numbers, number_to_find, middle + 1, high)
		else:
			return findValue(numbers, number_to_find, low, middle - 1)
	
	else:
		return -1

코드가 이전 예시와 상당히 유사합니다.

먼저 high가 low보다 크거나 같은지 확인합니다. 조건이 만족되지 않으면 -1을 반환하고, 만족되면 이진 탐색을 시작합니다.

중간 값은 이전 예시와 동일한 방식으로 계산합니다. high에서 low를 뺀 후 2로 나눈 몫을 구하고, 거기에 low를 더합니다.

이후 if 문을 통해 탐색 방향을 결정합니다:

• 중간 값이 찾는 숫자와 같은 경우 → 해당 숫자의 위치를 반환합니다.
• 중간 값이 찾는 숫자보다 작은 경우 → findValue() 함수를 다시 호출하며, 이때 low를 middle + 1로 설정합니다.
• 중간 값이 찾는 숫자보다 큰 경우 → findValue() 함수를 호출하며, 이때 high를 middle - 1로 설정합니다.

메인 프로그램 작성하기

이제 메인 프로그램만 작성하면 됩니다:

numbers = [7, 9, 14, 22, 34]
number_to_find = 22

final = findValue(numbers, number_to_find, 0, len(numbers) - 1)

if final == -1:
	print("This item was not found in the list.")
else:
	print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")

메인 프로그램은 이전 예시와 거의 같지만 한 가지 차이점이 있습니다. 바로 findValue() 함수에 low와 high라는 두 개의 새로운 매개변수를 함께 전달한다는 점입니다.

이렇게 해야 하는 이유는 알고리즘이 재귀 방식이기 때문입니다. 만약 함수 내부에서 low와 high 값을 초기화하면, 함수가 실행될 때마다 값이 리셋되어 탐색 알고리즘이 제대로 작동하지 않게 됩니다.

실행 결과는 다음과 같습니다:

The number 22 was found at index position 3.

이전과 동일한 결과를 얻었습니다. 이번에는 반복문 대신 재귀 프로그램으로 이진 탐색을 수행한 것입니다.

언제 파이썬 이진 탐색을 사용해야 할까?

이진 탐색은 숫자 리스트를 검색하는 매우 효율적인 방법입니다. 처음부터 끝까지 하나씩 확인하는 선형 탐색(linear search)보다 훨씬 빠른데, 그 이유는 정렬된 리스트의 중간을 확인하는 순간 탐색 범위가 절반으로 줄어들기 때문입니다.

단, 한 가지 중요한 점이 있습니다. 이진 탐색을 적용하려면 리스트가 반드시 숫자 순서대로 정렬되어 있어야 합니다. 이진 탐색을 수행하기 전에 숫자들이 오름차순으로 정렬되어 있는지 꼭 확인하세요.

파이썬 이진 탐색의 시간 복잡도

이진 탐색의 시간 복잡도는 얼마나 될까요? 좋은 질문입니다.

• 최선의 경우(Best Case): O(1) — 첫 번째 비교에서 바로 찾고자 하는 항목을 발견했을 때입니다.
• 평균 및 최악의 경우(Average/Worst Case): O(log n) — 탐색에 걸리는 시간이 리스트의 항목 수에 따라 로그적으로 증가한다는 의미입니다.

예를 들어 100만 개의 항목이 있는 리스트에서도 이진 탐색은 약 20번의 비교만으로 원하는 값을 찾을 수 있습니다. 이것이 이진 탐색이 강력한 이유입니다.

결론

이진 탐색은 리스트에서 특정 값의 인덱스 위치를 찾는 효율적인 방법입니다.

이진 탐색이 실행될 때마다 리스트는 두 부분으로 나뉘고, 탐색은 찾으려는 숫자가 있는 쪽에 집중됩니다. 따라서 탐색이 반복될수록 확인해야 할 숫자의 개수는 절반씩 줄어듭니다.

정렬된 데이터에서 특정 값을 빠르게 찾아야 한다면, 이진 탐색은 반드시 익혀야 할 필수 알고리즘입니다. 오늘 배운 반복 방식과 재귀 방식 두 가지 모두 직접 구현해 보면서 확실하게 익혀보세요!