이진 탐색 알고리즘

이진 탐색

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법입니다.

이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정합니다.

예시

이미 정렬된 10개의 데이터 중 값이 4인 원소를 찾는 예시를 살펴봅시다.

[Step 1] 시작점 : 0, 끝점 : 9, 중간점 : 4 (소수점 이하 제거)
이때 중간점인 8이 4보다 크므로 끝점을 3으로 바꿉니다.

[Step 2] 시작점 : 0, 끝점 : 3, 중간점 : 1 (소수점 이하 제거)

[Step 2] 시작점 : 2, 끝점 : 3, 중간점 : 2 (소수점 이하 제거)

이렇게 탐색 범위를 절반씩 줄여가며 탐색하는 방법을 이진 탐색이라고 합니다.

시간 복잡도

단계마다 탐색 범위를 2로 나누는 것과 동일하므로 밑이 2인 로그, log2 N에 비례합니다.

소스코드

위 예시의 이진 탐색 함수 코드는 다음과 같습니다.

# 이진 탐색
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)

라이브러리

• bisect_left(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
• bisect_right(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환