🌈Intro

데이터를 차례대로 탐색하는 순차 탐색 이 있지만, 이진 탐색을 사용하는 이유는 원소가 정렬된 조건이라면 더 빠르게 특정 데이터를 찾을 수 있기 때문이다. 반으로 나누면서 탐색하는 탐색 과정인데, 위치를 나타내는 변수를 사용해 원하는 데이터를 찾는 것이 이진 탐색 과정이라고 할 수 있다. 특히 파이썬에서는 외부 라이브러리인 Bisect 라이브러리를 사용해 이진 탐색을 더욱 효율적으로 수행할 수 있다.

🔍이진 탐색

파이썬 이진 탐색 라이브러리 bisect

bisect 는 이진 탐색 알고리즘을 구현한 모듈으로, 파이썬에서 가장 자주 쓰이는 라이브러리이다.
1. bisect_left(array, value) : 정렬 순서를 유지하면서 배열 array에 value를 삽입할 가장 왼쪽 인덱스 반환
2. bisect_right(array, value) : 정렬 순서를 유지하면서 배열 array에 value를 삽입할 가장 오른쪽 인덱스 반환
3. bisect.insort(array, value) : 정렬된 순서로 값을 삽입한다.

예제로 알아보면 다음과 같다. 먼저 이진 탐색을 통해 값의 위치를 알아내는 코드이다.

from bisect import bisect_right, bisect_left

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a, x)) # 2 => 가장 왼쪽 인덱스
print(bisect_right(a, x)) # 4 => 가장 오른쪽 인덱스

이를 이용해서 값이 특정 범위에 속하는 데이터의 개수를 구하는 경우도 함께 구할 수 있다.

from bisect import bisect_right, bisect_left

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a, x)) # 2 => 가장 왼쪽 인덱스
print(bisect_right(a, x)) # 4 => 가장 오른쪽 인덱스

이진 탐색 코드

파이썬은 bisect라는 라이브러리가 있지만, 물론 이러한 라이브러리 없이도 이진 탐색 구현이 가능하다.
이진 탐색의 과정을 보도록 하면,

이렇게 중간점이 찾는 원소와 같을 경우 탐색을 종료하게 되는데 절반씩 데이터가 줄어들도록 만든 점에서 퀵 정렬과 공통점이 있다. 하지만 퀵 정렬은 데이터가 정렬되지 않은 상태에서 수행하는 정렬 알고리즘이기 때문에 알고리즘을 수행하는 시간에 큰 차이가 있지만, 이진 탐색 알고리즘은 한 단계를 거칠 때마다 확인하는 원소가 절반으로 줄어든다.
일단 재귀함수를 통해 구현한 코드를 보면

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)