이진 탐색(Binary Search)

1. 이진 탐색(Binary Search)란?

 

• 정렬된 리스트를 반으로 나누어 필요한 부분으로 범위를 제한하여 값을 찾아가는 방식
• 찾고자 하는 범위가 넓은 경우 매우 효율적으로 사용이 가능

 

https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

 

2. 이진 탐색(Binary Search)조건

 

• 원소가 오름차순이든 내림차순이든 정렬이 되어있어야 한다.
• 원소에 랜덤으로 값을 접근할 수있어야 한다.

 

3. 이진 탐색(Binary Search)특징

 

 이진 탐색을 사용하면 일반적인 선형 탐색을 시행하는 것에 비해서 시간 복잡도가 훨씬 줄어든다. 적은 양의 데이터의 경우 모든 값들을 탐색하는데 그렇게 많은 시간이 소요되진 않는다. 하지만 데이터의 갯수가 100만개 이상 등 많은 데이터들 중에서 내가 원하는 값을 찾는 경우 선형 탐색의 경우는 1~100만 까지 모든 수를 탐색해보며 값을 찾아본다.

 

num_list = []
for i in range(10**7+1):
	num_list.append(i)

targets = [560000, 999999]

for i in targets:
	if i in num_list:
    	print("find")

 

 위의 예시 코드를 보면 target이 되는 값을 찾기위해 1부터 '560000' 까지 탐색하고 두번째 target 값을 찾기위해 '999999' 까지  탐색을 하게된다. 만약 target 값들이 더 많을경우 선형 탐색(Linear Search)을 사용할 경우 소요되는 시간은 매우 커지게 된다. ( O(n) *O(n) ) 이러한 경우 이진 탐색(Binary Search) 을 사용하면 소요되는 시간을 무척이나 줄일 수 있다.

 

num_list = []
for i in range(10**7+1):
	num_list.append(i)

targets = [560000, 999999]

for i in targets:
    end = 10**7
    start = 0
    mid = 0
    while (end-start>= 0):
        if i > num_list[mid]:
            start = mid + 1
        elif i < num_list[mid]:
            end = mid -1
        else:
        	print("find")
            break
        mid = (start+end)//2

 

• 위에 나온 코드를 이진 탐색 방식으로 변경해 보았다. 시작과 끝을 0 과 맨 마지막 값으로 설정한 후 중앙값을 둘의 합을 2로 나눈 값으로 설정한다.
• end-start >= 0 인 경우까지 반복문 시행 하며 중앙 값을 기준으로 큰지 작은지 판단을 한다.
• 값이 원하는 값인 경우 break를 통해서 반복문을 멈춘다.

 

위 같은 방식으로 계속해서 중앙값을 갱신해가며 원하는 값을 찾는 방식이 이진 탐색(Binary Search)이다. 이 방식이 선형 탐색(Linear Search)보다 빠른 이유는 한번 반복문을 시행할 때 마다 리스트 길이의 절반을 무시해가며 탐색을 진행하기 때문이다. 탐색해야할 값이 얼마나 크게 잡히든 크기의 대소를 비교하여 target 과 관련없는 리스트 부분을 무시해 버리기 때문에 몇번의 탐색만 거쳐도 목표값을 찾을 수 있다.

 

4. 이진 탐색(Binary Search)과 선형 탐색(Linear Search)의 차이

	이진 탐색(Binary Search)	선형 탐색(Linear Search)
특징	정렬되어있는 리스트에서 특정한 값을 찾을 때, 중간 값을 기준으로 대소를 비교해가며 특정 값을 찾는 알고리즘	찾고자 하는 값을 리스트의 맨 앞부터 끝까지 차례대로 찾아 나가는 것
장점	- 검색이 반복될 때마다 목표 값을 찾는 속도가 빨라짐	- 구현이 쉽다. - 정렬이 되지 않아도 사용이 가능하다.
단점	- 정렬된 리스트에만 사용할 수 있음	- 리스트 길이가 길어지면(데이터가 많은 경우) 탐색이 비효율적이다.
시간 복잡도	O(logN)	O(N)

 

5. 기타

 

 Python에는 이진 탐색 라이브러리 bisect 가 존재한다.

import bisect

num_list = [1,2,3,4,5,6,7,8,9]
target = 5
b = bisect.bisect_left(num_list,target)
c = bisect.bisect_right(num_list,target)
print(b,c)
# 4 5

test = 8
test2 = 12
bisect.insort_left(num_list,target)
print(num_list)
# [1, 2, 3, 4, 5, 5, 6, 7, 8, 9]
bisect.insort_right(num_list,test)
print(num_list)
# [1, 2, 3, 4, 5, 5, 6, 7, 8, 8, 9]
bisect.insort_right(num_list,test2)
print(num_list)
# [1, 2, 3, 4, 5, 5, 6, 7, 8, 8, 9, 12]

 

• bisect_left(검색할 리스트, 목표값) 구조로 이루어 져있으며 target 값의 index를 찾아준다.
• bisect_right(검색할 리스트, 목표값) 구조로 이루어 져있으며 target 값의 index+1을 찾아준다.
• insort_left(검색할 리스트, 목표값) 구조로 이루어 져있으며 리스트에서 정렬할 수 있는 위치에 해당 항목을 삽입( left는 왼쪽부터 탐색하는 것 같다. )
• insort_right(검색할 리스트, 목표값) 구조로 이루어 져있으며 리스트에서 정렬할 수 있는 위치에 해당 항목을 삽입( right는 오른쪽부터 탐색하는 것 같다. )

 

 Python 에는 위의 함수같은 함수도 있다는 것을 알고 가면 좋을 것 같아서 찾아서 정리해봤다. 기본적으로 이러한 함수들을 사용하기 위해서는 어떠한 방식으로 동작하는지 익히고난 후 스스로 구현을 할 수 있다면 라이브러리를 쓰는 것이 좋다고 생각을 하는 편이다.