이진탐색, bisect_left, bisect_right

* 잘못된 정보가 있으면 말씀해주세요. 빠른 반영 하겠습니다!

 

이진탐색을 사용하면 O(logn)의 시간복잡도를 가지게 되는데요

[0, 10, 20, 30, 40, 41, 42, 42, 43, 44, 45, 50, 60, 61] 의 배열이 있다고 가정하겠습니다

50을 찾겠습니다.

 

1. 중간값 42와 50을 비교 -> 42보다 50이 큼 -> [42, 43, 44, 45, 50, 60, 61]에서 찾음

2. [42, 43, 44, 45, 50, 60]의 중간값 44 와 50을 비교 -> 44보다 50이 큼 -> [45, 50, 60, 61]에서 찾음

3. [45, 50, 60, 61] 의 중간값 60과 50을 비교 -> 60이 50보다 큼 -> [45, 50]에서 찾음

4. [45, 50]의 중간값 45와 50을 비교 -> 45가 50보다 작음 -> [50]에서 찾음

5. [50]의 중간값 50과 50을 비교 -> 찾음

 

이진 탐색이란 이름이 붙은 이유는 

배열의 크기가 절반씩 줄어들기 때문입니다.

배열의 크기가 14, 7, 4, 2, 1 로 절반씩 줄어드는 것을 확인할수 있습니다.

 

시간 복잡도를 살펴보자면 

연산의 횟수가 곧 시간 복잡도가 될것입니다.

 

N, N/2, N/4, N/8, .....1 로 줄어드는 것을 확인할 수 있고

1 에 2^x 를 하면 N이 될것입니다.

2^x = N 여기에 밑이 2인 log를 곱해주면

x = logN 가 되겠지요 

따라서 이진 탐색의 시간복잡도는 O(logN)이 되게 됩니다.

 

아래에서 코드로 살펴보겠습니다.

from bisect import bisect_left, bisect_right

# 재귀호출로 구현한 이진 탐색입니다.
def binary_search_with_recursion(array, target, start, end):
  mid = (start + end) // 2
  if array[mid] == target :
    return mid
  if array[mid] > target :
    return binary_search_with_recursion(array, target, start, mid - 1)
  elif array[mid] < target :
    return binary_search_with_recursion(array, target, mid, end)

# while문으로 구현한 이진 탐색입니다.
def binary_search_with_while(array, target):
  start, end = 0, len(array) - 1
  while start < end :
    mid = (start + end) // 2
    if array[mid] > target :
      end = mid - 1
    elif array[mid] < target :
      start = mid
    else :
      start = end = mid
  return end

array = [0, 10, 20, 30, 40, 41, 42, 42, 43, 44, 45, 50, 60, 61]

print(bisect_left(array, 50)) # 11
print(bisect_right(array, 50)) # 12
print(binary_search_with_recursion(array, 50, 0, len(array) - 1)) # 11
print(binary_search_with_while(array, 50)) # 11

 

이진탐색을 구현한 4개의 방법을 알아보겠습니다.

 

1번은 재귀호출로 구현한 코드

2번은 while문으로 구현한 코드

 

재귀 함수 호출과 while문을 선택해서 사용할 수 있는 경우라면 while문을 이용하여 구현하는것이 좋습니다.

재귀 함수 호출은 함수가 호출될때마다 함수의 매개변수에 대한 위치정보와 리턴 값에 대한 위치정보가 계속해서 쌓이게 됩니다

 

100   a = 3

99     b = 3

98     return = 1 (최종 나가는 위치)

97     a = 4

96     b = 4

95     return = 100

94     a = 5

95     b = 5

94     return = 97

 

이런식으로 (정확한 예시는 아닙니다. 좀 더 공부하고 잘 표현할수 있도록 수정할게요) 스택이 계속 차지하게 되고 스택이 터지면 스택 오버플로우가 발생할 거에요,

또한 함수가 호출되고 나서 종료될때 스택부분을 해제해야하는데 이것에 대한 오버헤드가 발생하게 될거에요. 미묘하지만 작은게 모이면 부하가 걸릴겁니다.

 

반복문은 지역변수들이 호출될때 한번만 할당되기 때문에 그리고 스택내부에 할당된 변수들의 값만 반복문이 실행되면서 갱신해주기 때문에 다른 요인이 아닌 이상 스택이 터지는 경우는 발생하지 않을겁니다.

 

경우에 따라 사용하시면 될것 같아요. 저는 재귀호출을 선호합니다 ㅎㅎ 

 

3번은 bisect 라이브러리의 bisect_left 메소드

* 타겟값의 왼쪽 인덱스를 반환해 줍니다.

4번은 bisect 라이브러리의 bisect_right 메소드

* 타겟값의 왼쪽 인덱스를 반환해 줍니다.

 

https://docs.python.org/ko/3/library/bisect.html

bisect — 배열 이진 분할 알고리즘 — Python 3.10.0 문서