[알고리즘] 이분 탐색 - Binary Search

 이분 탐색 알고리즘 - 파이썬

 

이분 탐색은 값을 비교할 때마다 찾는 값이 있을 범위를 절반씩 좁히면서 탐색하는 효율적인 알고리즘이다. 이분 탐색에서 중요한 것은 '이미 정렬된 데이터'에서 값을 비교하면 찾는다는 것이다. 따라서 순차 탐색처럼 처음부터 하나씩 하는 것이 아니라 정렬된 데이터에서 기준점을 잡고 반으로 줄여나가며 찾는 것이기에 훨씬 효율적이고 빠른 알고리즘이다.

 

이분 탐색은 실생활에서 '책'을 떠올리면 쉽게 이해할 수 있다. 우리는 책을 이용해 원하는 것을 찾을 때 첫 페이지부터 찾는 것이 아니라, 중간쯤 쪽수를 찾아 펼친 다음 범위를 좁혀나가며 계속 찾아나간다. 원하는 페이지가 펼친 페이지보다 뒤에 있다면 앞쪽은 찾을 필요 없이 바로 뒤쪽부터 찾게 된다.

 

 

예제

def binary_search(a, x):
    start = 0
    end = len(a)-1

    while start <= end:
        mid = (start + end) // 2
        if(x == a[mid]): 	# 원하는 값 발견!
            return mid 
        elif (x > a[mid]): 	# 찾는 값이 더 크면, 오른쪽으로 범위를 좁혀 탐색
            start = mid + 1
        else:			# 찾는 값이 더 작으면, 왼쪽으로 범위를 좁혀 탐색
            end = mid - 1
            
    return -1			# 찾지 못했을 때

a = [1, 4, 9, 25, 36, 49] # 정렬된 자료
print(binary_search(a, 36)) # 5
print(binary_search(a, 12)) # -1