알고리즘 유형 5. 이분 탐색

선형탐색 Linear Search

 

앞에서부터 차례대로 찾는 것

# L에서 3찾기
L = [2, 5, 3, 4]

for i in L:
    if i == 3:
        break

 

 

 

 

이분탐색 Binary Search

 

탐색 범위를 절반으로 줄여가면서 찾는 것

# L에서 3찾기
L = [2, 3, 4, 5]

left = 0
right = len(L) - 1
mid = (left + right) // 2

while left <= right:
    if L[mid] == 3:
        break
    elif L[mid] > 3:
        right = mid - 1
    else: # L[mid] < 3
        left = mid + 1
    
    mid = (left + right) // 2

- 선형탐색보다 구현이 복잡하지만 시간이 짧게 걸립니다.

- 배열 안의 값들이 반드시 정렬되어 있어야 합니다.

 

 

이분탐색 라이브러리

from bisect import bisect_left, bisect_right

L = [2, 3, 6, 6, 6, 10, 12, 15]

l = bisect_left(L, 6) 
r = bisect_right(L, 6)
print(r - l)  #3

bisect_left()

정렬된 a에 x를 삽입할 위치를 리턴해준다.

x가 a에 이미 있으면 기존 항목의 앞(왼쪽)의 위치를 반환한다.

 

bisect_right()

정렬된 a에 x를 삽입할 위치를 리턴해준다.

x가 a에 이미 있으면 기존 항목의 뒤(오른쪽)의 위치를 반환한다.

 

bisect_right() - bisect_left() : 목표 값이 몇 개 있는지 알 수 있음 

 

 

 

 

매개변수탐색 Parametric Search

최적화 문제를 결정 문제로 바꿔 푸는 탐색 알고리즘

최적화 문제 Optimization Problem	결정 문제 Decision Problem
상황을 만족하는 변수의 최솟값, 최댓값을 구하는 문제	Yes, No 중 하나로 답할 수 있는 문제

- 이분 탐색 방식으로 어떤 두 그룹의 경계선을 찾아냅니다.

- 최종적으로 경계선의 왼쪽 범위를 택할지, 오른쪽 범위를 택할지 여부를 Yes/No 결정 문제의 결과로 정합니다.

- 파라메트릭 서치의 동작 방식은 사실상 이분탐색과 다를 바 없습니다.

- Binary Search와 Parametric Search의 차이점은, Binary Search에서는 배열에서 X와 일치하는 값을 찾으면 바로 함수를 종료하고 위치를 반환하지만, Parametric Search는 함수를 종료하지 않고 더 이상 살펴볼 배열이 남아있지 않을때까지 탐색을 계속합니다.

- 파라메트릭 서치 관련 문제

https://beluga9.tistory.com/375

2805번: 나무 자르기