[알고리즘] 이진 탐색

이진 탐색 (이분 탐색, Binary Search)

 

이진 탐색 트리와 같이 정렬된 리스트에서 탐색 범위를 두 부분으로 나누어 특정 값을 찾는 방식

 

앞이나 뒤에서부터 순서대로 원하는 값을 찾는 순차 탐색보다 훨씬 빠르다.

순차 탐색은 $O(N)$의 시간 복잡도를 가지나, 이진 탐색은 $O(logN)$의 속도를 가진다.

빠르기 때문에 효율성을 따져서 무언가를 찾는 문제에서 생각해 볼법하다.

 

알고리즘

• 우선 정렬된 리스트에서 최소값의 인덱스를 left, 최대값의 인덱스를 right로 둔다.
• left와 right를 통해 mid를 만들어준다.
• mid와 찾는 값$x$ 비교
• mid가 더 큰 경우 left = mid+1, mid가 더 작은 경우 right = mid-1
• 2, 3, 4번을 left>right가 될 때까지 반복

코드

import time
def BS(target, list_):
    left = 0
    right = len(myList)-1
    while left<right:
        mid = (left+right)//2
        if list_[mid] == target:
            return True
        elif list_[mid] > target:
            right = mid-1
        elif list_[mid] < target:
            left = mid+1
    return False

myList = list(range(1,999999,3))
target1 = 5513
start = time.time()
print(BS(target1,myList))
print(time.time()-start)

start = time.time()
for e in myList:
    if e == target1:
        print(True)
else:
    print(False)
print(time.time()-start)

확실한 차이는 아니지만 작은 데이터에서도 시간의 차이가 나는 것을  확인할 수 있다.