파이썬 리스트 이진 탐색 (Binary Search) / bisect 모듈

코딩테스트 스터디를 하면서 이번에 공부하게 된 이진 탐색에 대해 정리하려고 한다.

개념 자체는 엄청 간단하고 bisect라는 모듈이 있기 때문에 직접 구현하지 않아도 된다. 하지만 나는 몰라서 직접 구현했지.. 후후...

 

아래의 개념 포스팅은 <이것이 취업을 위한 코딩테스트다> 책을 참고하였습니다. (책 구매 링크)

1. 순차 탐색

• 말 그대로 우리가 찾고자 하는 대상을 앞에서부터 하나씩 순차적으로 확인하는 방법
• 시간만 충분하다면 무조건! 찾을 수 있음
• 우리가 알고 있는 for문, count 메서드 등이 여기에 해당 
• 시간 복잡도는 O(N) , 즉 N이 엄청 커지면 엄청 오래 걸린다는 단점 ..

2. 이진 탐색

• 이진 탐색을 하기 위해서는 시작점, 끝점, 중간점이 필요  → 찾으려는 대상과 중간점을 비교해가며 탐색하는 방법
• 중간점과 비교하기 때문에 탐색 범위를 절반씩 좁혀가면서 데이터를 찾는다. → 순차 탐색에 비해 매우 빠름
• 시간 복잡도는 O(log N), 정확히 말하면 \( log_2N \)에 비례한다.

 

이제 이진 탐색의 방법을 알아보쟝. 참고로 이진 탐색은 꼭 리스트가 정렬이 되어 있어야 한다!!

 

ex) [0, 2, 4, 6, 8, 10, 12, 14, 16, 18] 라는 리스트가 있을 때, 원소 4의 위치를 찾고 싶음

1. 중간점을 찾는다. 초기 시작점은 0, 끝점은 마지막 인덱스가 된다. 이 때 중간점은 말 그대로 시작점과 끝점의 중간 지점, 만약 0.5가 된다면 소수점은 버린다! → 이 예시에서는 시작점은 0, 끝점은 9, 중간점은 4 (중간은 4.5이지만 소수점을 버려서) 가 된다. 
2. 중간점에 있는 값과 목표값을 비교한다. → 리스트의 4번째 값은 8이다. 즉, 목표값보다 크다.
3. 우리가 원하는 목표값이 중간점에 있는 값보다 작으니, 중간점보다 큰 쪽은 볼 필요가 없음. 따라서, 끝 점을 중간점 '4' 앞인 '3' 으로 옮긴다.
4. 새로운 중간점은 (1)과 똑같은 방식으로 2가 된다.  → 리스트의 2번째 값은 4로 우리가 찾던 값이 나왔다!

* (3) 에서 만약 목표값이 중간점에 있는 값보다 클 경우에는, 끝점은 그대로 두고 시작점을 중간점 + 1만큼 해주면 된다.

 

위의 예시를 파이썬 코드로 작성하면 다음과 같다. (while문 이용)

array = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
target = 4

start = 0
end = len(array) - 1

while start <= end:
	mid = (start + end) // 2	# 얘 들여쓰기가 왜 이렇게 되징 ..
    if array[mid] == target:
    	print(mid)
    elif array[mid] > target:
    	end = mid - 1
    elif array[mid] < target:
    	start = mid + 1

위처럼 while문을 쓸 수도 있고, 재귀함수를 쓸 수도 있음! 

 

3. bisect 모듈 (참고) 

• 배열 이진 분할 알고리즘
• 정렬된 리스트를 삽입 후에 다시 정렬할 필요가 없도록 해줌 (이 말이 이해는 안 갔는데 예시를 보니 이해가 갔음)

ex1) 정렬된 배열에 현재 정렬된 상태를 유지하면서 n=5라는 원소를 추가하고 싶을 때

(1) 위에서 작성한 while문을 쓸 경우

array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

n = 5
start = 0
end = len(array) - 1
result = 0

while start <= end:
	mid = (start + end) // 2
    if array[mid] >= n:
    	result = mid
        end = mid - 1
    else:
    	start = mid + 1
        
print(result)
# 5

(2) bisect 모듈 사용

import bisect.bisect_left, bisect.bisect_right

array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 5
print(bisect.bisect_left(array, n))
print(bisect.bisect_right(array, n))
# 5 6

- 여기서 bisect.bisect_left 함수는 n을 array에 삽입할 위치를 찾을 때, 기존 항목이 있을 경우 (즉 n이랑 같은 값이 있을 경우), 그 항목의 왼쪽 값을 반환한다.

- bisect.bisect_right (혹은 그냥 bisect.bisect 를 써도 됨) 는 오른쪽 값 반환

- 같은 목적의 코드이지만 확실히 간결해진당. 내장 함수이기 때문에 코딩테스트에서도 활용 가능!

 

ex2) 정렬된 리스트에서 값이 특정 범위에 속하는 원소의 개수 

from bisect import bisect_left, bisect_right

def count_by_range(array, start, end):
	start_index = bisect_left(array, start)
    end_index = bisect_right(array, end)
    return end_index - start_index
    
array = [1, 2, 3, 3, 3, 3, 4, 4, 5, 7]

# 값이 4인 데이터 개수 출력
print(count_by_range(array, 4, 4))
# 2

# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(array, -1, 3))
# 6

특히 특정값의 개수를 찾는 문제에서, count 함수를 쓸 수 있지만, 만약 시간 복잡도가 정해져 있는 문제라면 꼭 이렇게 이진 탐색을 이용하여 풀어야 한다.