파이썬 - 이진탐색 (binary search)

이진탐색(binary search)은 '오름차순'으로 정렬된 리스트에서 사용할 수 있는 탐색법이다.

그림처럼 절반씩 줄여가면서 절반의 값과 탐색해야할 값을 비교해가면서 탐색하는 방식이다.

이진탐색은 최대 O(log N) 의 시간복잡도를 가졌다.

기본적인 형태는 아래와 같다.

재귀함수 형태

def binary(array, target ,start,end):

    if start > end:
        return None

    mid = (start+end)//2

    if array[mid] == target:
        return mid

    elif array[mid] >target:
        return binary(array,target,start,mid-1)

    else:
        return binary(array,target,mid+1,end)

반복문 형태

def binary_search(array, target, start, end):

	while start <= end:
    	mid = (start + end) // 2

      	if array[mid] == target:
      		return mid

      	elif array[mid] < target:
          	start = mid + 1
      	else:
          	end = mid -1
          
	return None

bisect 라이브러리

from bisect import bisect_left, bisect_right

a = [1,2,3,3,3,8,9]
x = 3

X1 = bisect_left(a,x) # 2
X2 = bisect_right(a,x) # 5

bisect_left, bisect_right 는 이진탐색으로 a에 x가 들어갈 인덱스를 각각 방향에 맞게 반환해준다.